【演算法篇】刷了兩道大廠面試題，含淚 」重學數組「
今日目錄：
1：能夠說出線性表的概念
2：能夠說出數組的存儲結構
3：能夠說出數組查詢，插入，刪除操作的特點及對應的時間複雜度
4：能夠完成動態數組ArrayList的程式碼編寫
1、線性表
在數據結構中，數據的邏輯結構分為線性結構和非線性結構。
線性結構：n個數據元素的有序（次序）集合。其特徵如下：
1．集合中必存在唯一的一個”第一個元素”；
2．集合中必存在唯一的一個”最後的元素”；
3．除最後元素之外，其它數據元素均有唯一的”後繼”；
4．除第一元素之外，其它數據元素均有唯一的”前驅”。
數據結構中線性結構指的是數據元素之間存在著「一對一」的線性關係的數據結構。當然這個線性並不是說一定是直線，常見的線性數據結構有：數組(一維)，鏈表，棧，隊列；它們也是我們後續學習其他數據結構的基礎，表現形式如下：
相對應於線性結構，非線性結構的邏輯特徵是一個結點元素可能對應多個直接前驅和多個後繼，比如後續要學習的：樹，圖，堆等，如下圖
2、數組基礎
2.1、概念和結構
數組（Array）是一種用連續的記憶體空間存儲相同數據類型數據的線性數據結構。
int[] array = new int[]{10,20,30}
int[] array = new int[6];
數組的表示方式：使用下標來獲取數組元素數據
思考一下操作平台是如何根據下標來找到對應元素的記憶體地址的呢？
我們拿一個長度為10的數組來舉例，int [] a= new int[10]，在下面的圖中，電腦給數組分配了一塊連續的空間，100-139，其中記憶體的起始地址為baseAddress=100
我們知道，電腦給每個記憶體單元都分配了一個地址，通過地址來訪問其數據，因此要訪問數組中的某個元素時，首先要經過一個定址公式計算要訪問的元素在記憶體中的地址：
a[i] = baseAddress + i * dataTypeSize其中dataTypeSize代表數組中元素類型的大小，在這個例子中，存儲的是int型的數據，因此dataTypeSize=4個位元組
下標為什麼從0開始而不是1呢？
從數組存儲的記憶體模型上來看，「下標」最確切的定義應該是「偏移（offset）」。前面也講到，如果用 array 來表示數組的首地址，array[0] 就是偏移為 0 的位置，也就是首地址，array[k] 就表示偏移 k 個type_size 的位置，所以計算 array[k] 的記憶體地址只需要用這個公式:
array[k]_address = base_address + k * type_size但是如果下標從1開始，那麼計算array[k]的記憶體地址會變成：
array[k]_address = base_address + (k-1)*type_size對比兩個公式，不難發現從數組下標從1開始如果根據下標去訪問數組元素，對於CPU來說，就多了一次減法指令。
當然另一方面也是由於歷史原因，c語言設計者使用0開始作為數組的下標，後來的高級語言沿用了這一設計。
2.2、數組的特點
2.2.1、查詢O(1)
數組元素的訪問是通過下標來訪問的，電腦通過數組的首地址和定址公式能夠很快速的找到想要訪問的元素
public int test01(int[] a,int i){
return a[i];
// a[i] = baseAddress + i * dataSize
}
程式碼的執行次數並不會隨著數組的數據規模大小變化而變化，是常數級的，所以查詢數據操作的時間複雜度是O(1)
2.2.2、插入刪除O(n)
數組是一段連續的記憶體空間，因此為了保證數組的連續性會使得數組的插入和刪除的效率變的很低。
數據插入：
假設數組的長度為 n，現在如果我們需要將一個數據插入到數組中的第 k 個位置。為了把第 k 個位置騰出來給新來的數據，我們需要將第 k～n 這部分的元素都順序地往後挪一位。如下圖所示：
插入操作對應的時間複雜度是多少呢？
最好情況下是O(1)的，最壞情況下是O(n)的，平均情況下的時間複雜度是O(n)。
數據刪除：
同理可得：如果我們要刪除第 k 個位置的數據，為了記憶體的連續性，也需要搬移數據，不然中間就會出現空洞，記憶體就不連續了，時間複雜度仍然是O(n)。
思考一下在什麼場景下用什麼辦法能提高數據刪除的效率呢？
實際上，在某些特殊場景下，我們並不一定非得追求數組中數據的連續性。如果我們將多次刪除操作集中在一起執行，刪除的效率是不是會提高很多呢？舉個例子
數組 a[6] 中存儲了 6 個元素：a1,a2,a3,a4,a5,a6。現在，我們要依次刪除 a1,a2 這兩個元素。
為了避免 a3,a4,a5,a6這幾個數據會被搬移兩次，我們可以先記錄下已經刪除的數據。每次的刪除操作並不是真正地搬移數據，只是記錄數據已經被刪除。當數組沒有更多空間存儲數據時，我們再觸發執行一次真正的刪除操作，這樣就大大減少了刪除操作導致的數據搬移。
對於這種思想，不就是 JVM 標記清除垃圾回收演算法的核心思想嗎？
這其實就是告訴我們，我們並不需要去死記硬背某個數據結構或者演算法，而是理解和學習它背後的思想和處理技巧。
3、面試實戰
3.1、11：盛最多水的容器
1：暴力破解，樸素解法
class Solution {
//暴力破解法 枚舉出所有坐標的組合,求出每個組合
public int maxArea(int[] height) {
//定義容納水的最大值
int max = 0 ;
for (int i=0; i<height.length;i++) {
for (int j=i+1;j<height.length;j++) {
int area = (j-i) * Math.min(height[i], height[j]);
max = Math.max(max, area);
}
}
return max;
}
}
2：雙指針（左右指針）（雙指針夾逼）
class Solution {
public int maxArea(int[] height) {
//定義最大水的值
int res = 0;
//定義雙指針
int i=0;
int j= height.length -1;
while (i!=j) {
int rest = Math.min(height[i],height[j]) * (j - i);
if ( height[i] < height[j] ) {
i++;
}else {
j--;
}
res = res > rest ? res:rest;
}
return res;
}
}
3.2、283：移動零
1：雙指針（快慢指針），一維數組的下標變換操作思想
class Solution {
// 雙指針移動 時間複雜度O(n) 空間複雜度O(1)
public void moveZeroes(int[] nums) {
if (nums == null || nums.length < 2) {
return;
}
//從前到後非零元素的指針
int p1 = 0;
for (int i =0; i < nums.length; i++) {
if (nums[i] != 0) {
nums[p1] = nums[i];
p1++;
}
}
while (p1 < nums.length) {
nums[p1] = 0;
p1++;
}
}
}
注意查看精選題解，還有一次循環解決問題的解法
4、動態數組
4.1、需求
設計一個基於數組的集合容器，滿足以下條件：
1：java中直接操作數組雖然獲取數據比較方便，但是插入刪除比較麻煩；因此容器要屏蔽（封裝）底層的數組操作細節，支援數據的查詢，插入，刪除操作
2：java中的數組類型一旦申請之後大小是不可變的，而容器需要支援動態擴容
4.2、實現
基於java語言的特性，我們先定義介面，面向介面編程
（1）定義容器介面com.itheima.array.inf.List
package com.itheima.array.inf;
/**
* Created by 傳智Podcast*黑馬程式設計師.
*/
public interface List {
/**
* 返回容器中元素的個數
* @return
*/
int size();
/**
* 判斷容器是否為空
* @return
*/
boolean isEmpty();
/**
* 查詢元素在容器中的索引下標
* @param o 元素對象
* @return 在容器中的下標 不存在則返回-1
*/
int indexOf(int o);
/**
* 判斷容器是否包含某個特定的元素
* @param e
* @return
*/
boolean contains(int e);
/**
* 將元素添加到容器結尾
* @param e 要添加的元素
* @return 是否添加成功
*/
boolean add(int e);
/**
* 向指定位置添加元素，該位置及以後的元素後移
* @param index 位置下標
* @param element 元素對象
*/
void add(int index, int element);
/**
* 用指定的元素替換指定位置的數據
* @param index 指定的位置索引下標
* @param element 新的元素
* @return 原始的元素
*/
int set(int index, int element);
/**
* 獲取指定位置的元素
* @param index 索引下標
* @return 該位置的元素
*/
int get(int index);
/**
* 移除指定位置的元素
* @param index 索引下標
* @return 被移除的元素
*/
int remove(int index);
/**
* 清除容器中所有元素
*/
void clear();
}
（2）創建介面的實現類：com.itheima.array.ArrayList並且實現List介面。
（3）我們的集合容器底層要基於數組存儲數據，因此定義成員數組，另外還需要返回集合容器中元素的個數，因此定義一個代表元素個數的成員變數
//存儲元素的數組
int[] elementData;
//容器中元素個數
private int size;
（4）定義構造方法，在容器初始化時初始化數組，並定義一個初始化容量大小
//容器默認容量大小
private final int DEFAULT_CAPACITY = 10;
public ArrayList() {
this.elementData = new int[DEFAULT_CAPACITY];
}
並且還可以重載構造函數，初始化時可以指定數組容量
public ArrayList(int initCapaticy) {
if (initCapaticy > 0) {
this.elementData = new int[initCapaticy];
}else {
throw new IllegalArgumentException("initCapaticy error"+initCapaticy);
}
}
（5）完成size,isEmpty,indexOf,contains等方法
@Override
public int size() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public int indexOf(int o) {
for (int i=0; i < size; i++) {
if ( elementData[i] == o) {
return i;
}
}
return -1;
}
@Override
public boolean contains(int e) {
return indexOf(e) >=0;
}
（6）完成添加元素到容器尾部的方法add，這個過程中涉及到容器的動態擴容
@Override
public boolean add(int e) {
//添加之前先確保容量是否夠
ensureCapacity(size+1);
this.elementData[size++] = e;
return true;
}
private void ensureCapacity(int minCapacity) {
if (minCapacity > this.elementData.length) {
grow(minCapacity);
}
}
private void grow(int minCapacity) {
int oldCapacity = this.elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity < minCapacity) {
newCapacity = minCapacity;
}
//用新的容量大小創建新的數組,並將原數組中的數據拷貝到新數組中，並使得this.elementData指向新數組
copyOf(newCapacity);
}
private void copyOf(int newCapacity) {
int[] newarray = new int[newCapacity];
System.arraycopy(this.elementData,0,newarray,0,size);
this.elementData = newarray;
}
（7）完成add(int index, int element),set(int index, int element),get(int index)方法，方法中先檢查索引位置是否合理，然後檢查是否需要擴容，最後在指定索引位置插入元素
@Override
public void add(int index, int element) {
rangeCheck(index);
//因為要加一個元素，之前的元素不會被覆蓋，只會向後移動，所以可能在元素後移之前要先擴容
ensureCapacity(size+1);
//擴容完成後先將從index處的元素依次後移
System.arraycopy(this.elementData,index,this.elementData,index+1,size-index);
//在index位置存入數據
this.elementData[index] = element;
size++;
}
@Override
public int set(int index, int element) {
rangeCheck(index);
int oldElement = this.elementData[index];
this.elementData[index] = element;
return oldElement;
}
private void rangeCheck(int index) {
if (index < 0 || index >size) {
throw new IndexOutOfBoundsException("index:"+index+",size="+this.size);
}
}
@Override
public int get(int index) {
rangeCheck(index);
return this.elementData[index];
}
（8）完成remove(int index),clear
@Override
public int remove(int index) {
rangeCheck(index);
int oldValue = this.elementData[index];
//要移動元素的個數
int moveCount = size - index -1;
System.arraycopy(this.elementData,index+1,this.elementData,index,moveCount);
//清理最後一個位置的元素
this.elementData[size-1] = 0;
//容器中元素個數-1
size--;
return oldValue;
}
@Override
public void clear() {
for (int i = 0; i < size; i++) {
elementData[i] = 0;
}
size = 0;
}
（9）重寫一下ArrayList的toString方法，方便列印輸出
@Override
public String toString() {
//按照[1,2,3,5,6]的格式輸出數組中的元素
StringBuilder sb = new StringBuilder("[");
for (int i=0 ;i < size; i++) {
sb.append(this.elementData[i]).append(",");
}
sb.append("]");
return sb.toString();
}
（10）編寫測試類完成測試：com.itheima.array.ArrayListTest
package com.itheima.array;
import com.itheima.array.inf.List;
/**
* Created by 傳智Podcast*黑馬程式設計師.
*/
public class ArrayListTest {
public static void main(String[] args) {
List list = new ArrayList();
//添加數據
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.add(5);
System.out.println("索引為4的元素:"+list.get(4));
list.add(6);
list.add(7);
list.add(8);
list.add(9);
list.add(10);
//再添就要擴容了
list.add(11);
System.out.println("size="+list.size()+"--"+list);
System.out.println("是否包含8:"+list.contains(8)+",集合容器是否為空:"+list.isEmpty());
list.add(12);
list.add(13);
list.add(14);
list.add(15);
//既要擴容，元素又要後移
list.add(13,141);
System.out.println("size="+list.size()+"--"+list);
int set = list.set(13, 142);
System.out.println("set方法返回的值:"+set+"--完成後的list:"+list);
int remove = list.remove(13);
System.out.println("remove方法返回的值:"+remove+"--remove後的list:"+list);
list.clear();
System.out.println("clear之後:"+list);
}
}
思考一下課後完成：將ArrayList改造成能存儲任意jiava類型數據的容器，應該如何完成？
提示：將int類型的數組變換成Object類型的數組，然後改造相應的介面方法，添加泛型
作為高級語言編程者，是不是數組就無用武之地了呢？
當然不是，有些時候，用數組會更合適些，我總結了幾點自己的經驗。
1.Java ArrayList 無法存儲基本類型，比如 int、long，需要封裝為 Integer、Long 類，而 Autoboxing、Unboxing 則有一定的性能消耗，所以如果特別關注性能，或者希望使用基本類型，就可以選用數組。
2.如果數據大小事先已知，並且對數據的操作非常簡單，用不到 ArrayList 提供的大部分方法，也可以直接使用數組。
總結一下就是說：對於業務開發，直接使用容器就足夠了，省時省力。畢竟損耗一丟丟性能，完全不會影響到系統整體的性能。但如果你是做一些非常底層的開發，比如開發網路框架，性能的優化需要做到極致，這個時候數組就會優於容器，成為首選。
本文由傳智教育博學谷 – 狂野架構師教研團隊發布
如果本文對您有幫助，歡迎關注和點贊；如果您有任何建議也可留言評論或私信，您的支援是我堅持創作的動力
轉載請註明出處！
