【數(shù)據(jù)結(jié)構(gòu)與算法】數(shù)組的增刪改查
前言
作為重要的線性數(shù)據(jù)結(jié)構(gòu)， 我們經(jīng)常會(huì)跟數(shù)組打交道。所謂數(shù)組，就是一系列相同數(shù)據(jù)類(lèi)型元素的集合，數(shù)據(jù)類(lèi)型可以是 int、float、String、類(lèi)……。而對(duì)數(shù)組的增刪改查則是日常用到的操作。為了弄清楚這些常用操作，此博客則對(duì)這些操作進(jìn)行一一梳理。
數(shù)組簡(jiǎn)介
如何創(chuàng)建數(shù)組
我們以 Java 中創(chuàng)建數(shù)組為例，創(chuàng)建語(yǔ)法如下：
dataType[] arrName = new dataType[size];
其中各個(gè)字段的含義如下：
dataType：也就是我們數(shù)組中元素的數(shù)據(jù)類(lèi)型；arrName：即數(shù)組名；size：即數(shù)組所能容納的元素?cái)?shù)量；new：Java 語(yǔ)言中的關(guān)鍵詞；
假設(shè)我們要?jiǎng)?chuàng)建一個(gè)由 10 個(gè)元素的數(shù)組，其中元素的數(shù)據(jù)類(lèi)型為 int，則創(chuàng)建的方法如下：
int[] arr = new int[10];
創(chuàng)建數(shù)組時(shí)，我們一定要注意，必須明確指定數(shù)組的元素個(gè)數(shù)，也就是上邊說(shuō)的 size。
數(shù)組長(zhǎng)度與容量
在我們?nèi)粘Ｊ褂弥?，大家都容易把這兩個(gè)概念混為一談，但是實(shí)際上，兩者是不一樣的，兩者的定義如下：
容量：指當(dāng)前數(shù)組最多能容納的元素個(gè)數(shù)，也就是我們創(chuàng)建數(shù)組時(shí)所指定的元素個(gè)數(shù)； 長(zhǎng)度：指當(dāng)前數(shù)組中的元素個(gè)數(shù)，它不一定等于容量，小于容量時(shí)表示數(shù)組還可以添加元素； 兩者關(guān)系：長(zhǎng)度 <= 容量；
int[] arr = new int[10];
length = 0;
for(int i = 0; i < 5; i++){
arr[length++] = i + 1;
}
System.out.println(“數(shù)組容量： ” + arr.length)；
System.out.println(“數(shù)組長(zhǎng)度： ” + length；
插入元素到數(shù)組
要插入元素到數(shù)組中，可以分為如下 3 種情況：
插入數(shù)組開(kāi)頭 插入數(shù)組結(jié)尾 插入數(shù)組中間
插入元素到數(shù)組開(kāi)頭
要將元素插入數(shù)組開(kāi)頭位置，我們只需要先把原來(lái)數(shù)組的元素整體都向后移動(dòng)一個(gè)位置，然后將插入元素賦值給數(shù)組第一個(gè)元素即可；
/**
* 插入元素到數(shù)組開(kāi)頭
* @param arr 待插入元素的數(shù)組
* @param val 待插入的元素
* @return 插入元素后的數(shù)組
*/
public int[] insertStart(int[] arr, int val){
// 用于存放插入元素后的數(shù)據(jù)
int[] destArr = new int[arr.length + 1];
// 將元素插入新數(shù)組開(kāi)頭，同時(shí)將原數(shù)組整體賦值給新數(shù)組
destArr[0] = val;
for(int i = 0; i < arr.length; i++){
destArr[i + 1] = arr[i];
}
return destArr;
}
插入元素到數(shù)組結(jié)尾
這是最簡(jiǎn)單的一種情況，要將元素插入到數(shù)組結(jié)尾，直接將插入的元素賦值給數(shù)組尾部即可；
/**
* 插入元素到數(shù)組開(kāi)頭
* @param arr 待插入元素的數(shù)組
* @param val 待插入的元素
* @return 插入元素后的數(shù)組
*/
public int[] insertEnd(int[] arr, int val){
// 用于存放插入元素后的數(shù)據(jù)
int[] destArr = new int[arr.length + 1];
// 將元素插入新數(shù)組結(jié)尾，同時(shí)將原數(shù)組整體賦值給新數(shù)組
destArr[arr.length] = val;
for(int i = 0; i < arr.length; i++){
destArr[i] = arr[i];
}
return destArr;
}
插入元素到數(shù)組中間
插入元素到中間，相當(dāng)于只要先把數(shù)組中插入位置后邊的元素整體向后移動(dòng)一位，然后將插入元素賦值給對(duì)應(yīng)插入位置的數(shù)組對(duì)應(yīng)位置即可；
/**
* 插入元素到數(shù)組任意位置
* @param arr 待插入元素的數(shù)組
* @param val 待插入的元素
* @param index 待插入元素的索引位置
* @return 插入元素后的數(shù)組
*/
public int[] insertAnyWhere(int[] arr, int index, int val){
// 用于存放插入元素后的數(shù)據(jù)
int[] destArr = new int[arr.length + 1];
// 將原數(shù)組插入元素位置前半段賦值給新數(shù)組
for(int i = 0; i < index; i++){
destArr[i] = arr[i];
}
// 將原數(shù)組插入元素位置后半段賦值給新數(shù)組
for(int j = index; j < arr.length; j++){
destArr[j + 1] = arr[j];
}
// 將元素插入新數(shù)組指定位置
destArr[index] = val;
return destArr;
}
刪除數(shù)組中的元素
同樣的，假設(shè)我們要?jiǎng)h除數(shù)組中的元素，也要考慮如下 3 種情況：
刪除數(shù)組開(kāi)頭元素 刪除數(shù)組末尾元素 刪除數(shù)組中間元素
刪除數(shù)組開(kāi)頭元素
刪除開(kāi)頭元素，相當(dāng)于將原數(shù)組開(kāi)頭元素后邊的元素整體向前移動(dòng)一位，而不用管開(kāi)頭的元素；
/**
* 刪除數(shù)組開(kāi)頭元素
* @param arr 待刪除元素的數(shù)組
* @return 刪除元素后的數(shù)組
*/
public int[] deleteStart(int[] arr){
// 刪除元素后，數(shù)組容量減小
int[] destArr = new int[arr.length - 1];
// 刪除開(kāi)頭元素，相當(dāng)于將后邊的元素整體向前移動(dòng)一位
for(int i = 1; i < arr.length; i++){
destArr[i - 1] = arr[i];
}
return destArr;
}
刪除數(shù)組末尾元素
直接將數(shù)組末尾元素刪除即可；
/**
* 刪除數(shù)組末尾元素
* @param arr 待刪除元素的數(shù)組
* @return 刪除元素后的數(shù)組
*/
public int[] deleteEnd(int[] arr){
// 刪除元素后，數(shù)組容量減小
int[] destArr = new int[arr.length - 1];
// 刪除最后一個(gè)元素，相當(dāng)于不去管最后一個(gè)元素
for(int i = 0; i < arr.length - 1; i++){
destArr[i] = arr[i];
}
return destArr;
}
刪除數(shù)組中間元素
刪除任意位置元素，相當(dāng)于不動(dòng)刪除位置前的元素，然后將刪除元素位置后的元素整體向前移動(dòng)一位；
/**
* 刪除數(shù)組任意位置元素
* @param arr 待刪除元素的數(shù)組
* @param index 待刪除元素索引位置
* @return 刪除元素后的數(shù)組
*/
public int[] deleteMiddle(int[] arr, int index){
// 刪除元素后，數(shù)組容量減小
int[] destArr = new int[arr.length - 1];
// 刪除任意位置元素，前半段保持
for(int i = 0; i < index; i++){
destArr[i] = arr[i];
}
// 后半段整體向前移動(dòng)一位
for(int j = index; j < arr.length - 1; j++){
destArr[j] = arr[j + 1];
}
return destArr;
}
修改數(shù)組元素
要修改數(shù)組元素，實(shí)際上只要知道需要修改數(shù)組元素的索引位置即可，然后將對(duì)應(yīng)索引位置的值修改為你要修改的值即可；
/**
* 修改數(shù)組任意位置元素
* @param arr 待修改元素的數(shù)組
* @param index 待修改元素索引位置
* @param val 修改后的元素值
* @return 修改元素后的數(shù)組
*/
public int[] update(int[] arr, int index, int val){
arr[index] = val;
return arr;
}
查找數(shù)組中的元素
要查找數(shù)組中的某一個(gè)元素，最常用的方法有如下兩種：
線性查找，主要針對(duì)數(shù)組較小時(shí) 二分查找，主要針對(duì)數(shù)組較大時(shí)，提高查詢效率
線性查找
線性查找即遍歷數(shù)組，然后判斷各元素是否是目標(biāo)值，是則輸出對(duì)應(yīng)索引位置，否則返回 -1，此時(shí)時(shí)間復(fù)雜度為 ；
/**
* 線性查找
* @param array
* @param target 要查找的目標(biāo)值
* @return -1 說(shuō)明未找到目標(biāo)值，否則返回目標(biāo)值索引位置
*/
public int linearSearch(int[] array, int target) {
// 查找到目標(biāo)值時(shí)，返回目標(biāo)索引位置
for(int i = 0; i < array.length; i++){
if(target == array[i]){
reurn i;
}
}
return -1;
}
二分查找
當(dāng)數(shù)組長(zhǎng)度很小時(shí)，使用線性查找方法很快就能找到目標(biāo)值是否存在并返回對(duì)應(yīng)索引位置，但當(dāng)數(shù)組很大時(shí)，線性查找的方法效率就太低了。這時(shí)候二分查找是更理想的查找手段，二分查找實(shí)質(zhì)是使用雙指針，每次對(duì)半查找，大大提高效率，時(shí)間復(fù)雜度縮減為 ；
/**
* 二分查找
* @param array
* @param target 要查找的目標(biāo)值
* @return -1 說(shuō)明未找到目標(biāo)值，否則返回目標(biāo)值索引位置
*/
public int binarySearch(int[] array, int target) {
// 左右指針
int left = 0;
int right = array.length - 1;
while(left <= right) {
int mid = left + (right - left) / 2;
// 當(dāng)前值等于目標(biāo)值時(shí)，返回當(dāng)前索引位置
if(array[mid] == target){
return mid;
} else if (array[mid] < target){ // 當(dāng)前值小于目標(biāo)值，左指針向右移動(dòng)一位
left = mid + 1;
} else { // 當(dāng)前值大于目標(biāo)值，右指針向左移動(dòng)一位
right = mid - 1;
}
}
return -1;
}
總結(jié)
今天的內(nèi)容到此結(jié)束，主要針對(duì)數(shù)組這一數(shù)據(jù)結(jié)構(gòu)進(jìn)行了介紹，講了如何創(chuàng)建數(shù)組，并對(duì)數(shù)組中易混淆的長(zhǎng)度和容量概念進(jìn)行了比較。最后則是講了數(shù)組的相關(guān)操作，總結(jié)了幾種針對(duì)數(shù)組的增刪改查方法。
如果你有更多關(guān)于數(shù)組的相關(guān)知識(shí)，歡迎評(píng)論區(qū)留言交流，咱們?cè)u(píng)論區(qū)見(jiàn)！
