关于数据结构和算法:数据结构与算法数组的增删改查

前言

作为重要的线性数据结构，咱们常常会跟数组打交道。所谓数组，就是一系列雷同数据类型元素的汇合，数据类型能够是 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 中状况：

1. 插入数组结尾
2. 插入数组结尾
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 种状况：

1. 删除数组结尾元素
2. 删除数组开端元素
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. 线性查找，次要针对数组较小时
2. 二分查找，次要针对数组较大时，进步查问效率

线性查找

线性查找即遍历数组，而后判断各元素是否是目标值，是则输入对应索引地位，否则返回 -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;
}

总结

明天的内容到此结束，次要针对数组这一数据结构进行了介绍，讲了如何创立数组，并对数组中易混同的长度和容量概念进行了比拟。最初则是讲了数组的相干操作，总结了几种针对数组的增删改查办法。

如果你有更多对于数组的相干常识，欢送评论区留言交换，咱们评论区见！