数据结构与算法 | 数组的增删改查

前言

作为重要的线性数据结构，我们经常会跟数组打交道。所谓数组，就是一系列相同数据类型元素的集合，数据类型可以是 int、float、String、类……。而对数组的增删改查则是日常用到的操作。为了弄清楚这些常用操作，此博客则对这些操作进行一一梳理。

数组简介

如何创建数组

我们以 Java 中创建数组为例，创建语法如下：

dataType[] arrName = new dataType[size];

其中各个字段的含义如下：

dataType：也就是我们数组中元素的数据类型；
arrName：即数组名；
size：即数组所能容纳的元素数量；
new：Java 语言中的关键词；

假设我们要创建一个由 10 个元素的数组，其中元素的数据类型为 int，则创建的方法如下：

int[] arr = new int[10];

创建数组时，我们一定要注意，必须明确指定数组的元素个数，也就是上边说的 size。

数组长度与容量

在我们日常使用中，大家都容易把这两个概念混为一谈，但是实际上，两者是不一样的，两者的定义如下：

容量：指当前数组最多能容纳的元素个数，也就是我们创建数组时所指定的元素个数；
长度：指当前数组中的元素个数，它不一定等于容量，小于容量时表示数组还可以添加元素；
两者关系：长度 <= 容量；

int[] arr = new int[10];
length = 0;
for(int i = 0; i < 5; i++){
    arr[length++] = i + 1;
}

System.out.println(“数组容量： ” + arr.length)；
System.out.println(“数组长度： ” + length；

插入元素到数组

要插入元素到数组中，可以分为如下 3 中情况：

插入数组开头
插入数组结尾
插入数组中间

插入元素到数组开头

要将元素插入数组开头位置，我们只需要先把原来数组的元素整体都向后移动一个位置，然后将插入元素赋值给数组第一个元素即可；

/**
* 插入元素到数组开头
* @param arr 待插入元素的数组
* @param val 待插入的元素
* @return 插入元素后的数组
*/
public int[] insertStart(int[] arr, int val){
    // 用于存放插入元素后的数据
    int[] destArr = new int[arr.length + 1];
    
    // 将元素插入新数组开头，同时将原数组整体赋值给新数组
    destArr[0] = val;
    for(int i = 0; i < arr.length; i++){
        destArr[i + 1] = arr[i];
    }
    
    return destArr;
}

插入元素到数组结尾

这是最简单的一种情况，要将元素插入到数组结尾，直接将插入的元素赋值给数组尾部即可；

/**
* 插入元素到数组开头
* @param arr 待插入元素的数组
* @param val 待插入的元素
* @return 插入元素后的数组
*/
public int[] insertEnd(int[] arr, int val){
    // 用于存放插入元素后的数据
    int[] destArr = new int[arr.length + 1];
    
    // 将元素插入新数组结尾，同时将原数组整体赋值给新数组
    destArr[arr.length] = val;
    for(int i = 0; i < arr.length; i++){
        destArr[i] = arr[i];
    }
    
    return destArr;
}

插入元素到数组中间

插入元素到中间，相当于只要先把数组中插入位置后边的元素整体向后移动一位，然后将插入元素赋值给对应插入位置的数组对应位置即可；

/**
* 插入元素到数组任意位置
* @param arr 待插入元素的数组
* @param val 待插入的元素
* @param index 待插入元素的索引位置
* @return 插入元素后的数组
*/
public int[] insertAnyWhere(int[] arr, int index, int val){
    // 用于存放插入元素后的数据
    int[] destArr = new int[arr.length + 1];
    
    // 将原数组插入元素位置前半段赋值给新数组
    for(int i = 0; i < index; i++){
        destArr[i] = arr[i];
    }
    // 将原数组插入元素位置后半段赋值给新数组
    for(int j = index; j < arr.length; j++){
        destArr[j + 1] = arr[j];
    }
    
    // 将元素插入新数组指定位置
    destArr[index] = val;
    
    return destArr;
}

删除数组中的元素

同样的，假设我们要删除数组中的元素，也要考虑如下 3 种情况：

删除数组开头元素
删除数组末尾元素
删除数组中间元素

删除数组开头元素

删除开头元素，相当于将原数组开头元素后边的元素整体向前移动一位，而不用管开头的元素；

/**
* 删除数组开头元素
* @param arr 待删除元素的数组
* @return 删除元素后的数组
*/

public int[] deleteStart(int[] arr){
    // 删除元素后，数组容量减小
    int[] destArr = new int[arr.length - 1];
    
    // 删除开头元素，相当与将后边的元素整体向前移动一位
    for(int i = 1; i < arr.length; i++){
        destArr[i - 1] = arr[i];
    }
    
    return destArr;
}

删除数组末尾元素

直接将数组末尾元素删除即可；

/**
* 删除数组末尾元素
* @param arr 待删除元素的数组
* @return 删除元素后的数组
*/

public int[] deleteEnd(int[] arr){
    // 删除元素后，数组容量减小
    int[] destArr = new int[arr.length - 1];
    
    // 删除最后一个元素，相当于不去管最后一个元素
    for(int i = 0; i < arr.length - 1; i++){
        destArr[i] = arr[i];
    }
    
    return destArr;
}

删除数组中间元素

删除任意位置元素，相当于不动删除位置前的元素，然后将删除元素位置后的元素整体向前移动一位；

/**
* 删除数组任意位置元素
* @param arr 待删除元素的数组
* @param index 待删除元素索引位置
* @return 删除元素后的数组
*/

public int[] deleteMiddle(int[] arr, int index){
    // 删除元素后，数组容量减小
    int[] destArr = new int[arr.length - 1];
    
    // 删除任意位置元素，前半段保持
    for(int i = 0; i < index; i++){
        destArr[i] = arr[i];
    }
    
    // 后半段整体向前移动一位
    for(int j = index; j < arr.length - 1; j++){
        destArr[j] = arr[j + 1];
    }
    
    return destArr;
}

修改数组元素

要修改数组元素，实际上只要知道需要修改数组元素的索引位置即可，然后将对应索引位置的值修改为你要修改的值即可；

/**
* 修改数组任意位置元素
* @param arr 待修改元素的数组
* @param index 待修改元素索引位置
* @param val 修改后的元素值
* @return 修改元素后的数组
*/

public int[] update(int[] arr, int index, int val){
    arr[index] = val;
    return arr;
}

查找数组中的元素

要查找数组中的某一个元素，最常用的方法有如下两种：

线性查找，主要针对数组较小时
二分查找，主要针对数组较大时，提高查询效率

线性查找

线性查找即遍历数组，然后判断各元素是否是目标值，是则输出对应索引位置，否则返回 -1，此时时间复杂度为 $O(n)$ ；

/**
* 线性查找
* @param array 
* @param target 要查找的目标值
* @return -1 说明未找到目标值，否则返回目标值索引位置
*/

public int linearSearch(int[] array, int target) {
    
    // 查找到目标值时，返回目标之索引位置
    for(int i = 0; i < array.length; i++){
    	if(target == array[i]){
            reurn i;
        }    
    }
        
    return -1;
}

二分查找

当数组长度很小时，使用线性查找方法很快就能找到目标值是否存在并返回对应索引位置，但当数组很大时，线性查找的方法效率就太低了。这时候二分查找是更理想的查找手段，二分查找实质是使用双指针，每次对半查找，大大提高效率，时间复杂度缩减为 $O(logn)$ ；

/**
* 二分查找
* @param array 
* @param target 要查找的目标值
* @return -1 说明未找到目标值，否则返回目标值索引位置
*/

public int binarySearch(int[] array, int target) {
    // 左右指针
    int left = 0; 
    int right = array.length - 1; 

    while(left <= right) {
        int mid = left + (right - left) / 2;
        // 当前值等于目标值时，返回当前索引位置
        if(array[mid] == target){
            return mid; 
        } else if (array[mid] < target){ // 当前值小于目标值，左指针向右移动一位
            left = mid + 1; 
        } else { // 当前值大于目标值，右指针向左移动一位
            right = mid - 1;
        }            
    }
    return -1;
}