【演演算法篇】刷了兩道大廠面試題，含淚 」重學陣列「
今日目錄：
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 傳智播客*黑馬程式設計師.
*/
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 傳智播客*黑馬程式設計師.
*/
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 提供的大部分方法，也可以直接使用陣列。
總結一下就是說：對於業務開發，直接使用容器就足夠了，省時省力。畢竟損耗一丟丟效能，完全不會影響到系統整體的效能。但如果你是做一些非常底層的開發，比如開發網路框架，效能的優化需要做到極致，這個時候陣列就會優於容器，成為首選。
本文由傳智教育博學谷 - 狂野架構師教研團隊釋出
如果本文對您有幫助，歡迎關注和點贊；如果您有任何建議也可留言評論或私信，您的支援是我堅持創作的動力
轉載請註明出處！