数组可以说是最基础、最简单的数据结构了。数组用一块连续的内存空间，来存储相同类型的一组数据，最大的特点就是支持随机访问，但插入、删除操作也因此变得比较低效，平均情况时间复杂度为 O(n)。在平时的业务开发中，我们可以直接使用编程语言提供的容器类，但是，如果是特别底层的开发，直接使用数组可能会更合适。

从数组存储的内存模型上来看，“下标”最确切的定义应该是“偏移（offset）”。前面也讲到，如果用 a 来表示数组的首地址，a[0]就是偏移为 0 的位置，也就是首地址，a[k]就表示偏移 k 个 type_size 的位置，所以计算 a[k]的内存地址只需要用这个公式：

但是，如果数组从 1 开始计数，那我们计算数组元素 a[k]的内存地址就会变为：

对比两个公式，我们不难发现，从 1 开始编号，每次随机访问数组元素都多了一次减法运算，对于 CPU 来说，就是多了一次减法指令。数组作为非常基础的数据结构，通过下标随机访问数组元素又是其非常基础的编程操作，效率的优化就要尽可能做到极致。所以为了减少一次减法操作，数组选择了从 0 开始编号，而不是从 1 开始。

总结：个人理解是因为计算机底层一开始定义的是从0进行，后续产生的编程语言在一定程度上都沿用了该方式。

我们拿一个长度为 10 的 int 类型的数组 int[] a = new int[10]来举例。计算机给数组 a[10]，分配了一块连续内存空间 1000～1039，其中，内存块的首地址为 base_address = 1000。

我们知道，计算机会给每个内存单元分配一个地址，计算机通过地址来访问内存中的数据。当计算机需要随机访问数组中的某个元素时，它会首先通过下面的寻址公式，计算出该元素存储的内存地址：

其中 data_type_size 表示数组中每个元素的大小。我们举的这个例子里，数组中存储的是 int 类型数据，所以 data_type_size 就为 4 个字节。

假设数组的长度为 n，现在，如果我们需要将一个数据插入到数组中的第 k 个位置。为了把第 k 个位置腾出来，给新来的数据，我们需要将第 k～n 这部分的元素都顺序地往后挪一位。那插入操作的时间复杂度是多少呢？

如果在数组的末尾插入元素，那就不需要移动数据了，这时的时间复杂度为 O(1)。但如果在数组的开头插入元素，那所有的数据都需要依次往后移动一位，所以最坏时间复杂度是 O(n)。 因为我们在每个位置插入元素的概率是一样的，所以平均情况时间复杂度为 (1+2+…n)/n=O(n)。

如果数组中的数据是有序的，我们在某个位置插入一个新的元素时，就必须按照刚才的方法搬移 k 之后的数据。但是，如果数组中存储的数据并没有任何规律，数组只是被当作一个存储数据的集合。在这种情况下，如果要将某个数据插入到第 k 个位置，为了避免大规模的数据搬移，我们还有一个简单的办法就是，直接将第 k 位的数据搬移到数组元素的最后，把新的元素直接放入第 k 个位置。

跟插入数据类似，如果我们要删除第 k 个位置的数据，为了内存的连续性，也需要搬移数据，不然中间就会出现空洞，内存就不连续了。

如果删除数组末尾的数据，则最好情况时间复杂度为 O(1)；如果删除开头的数据，则最坏情况时间复杂度为 O(n)；平均情况时间复杂度也为 O(n)。

实际上，在某些特殊场景下，我们并不一定非得追求数组中数据的连续性。如果我们将多次删除操作集中在一起执行，删除的效率是不是会提高很多呢？假如数组 a[10]中存储了 8 个元素：a，b，c，d，e，f，g，h。现在，我们要依次删除 a，b，c 三个元素。

为了避免 d，e，f，g，h 这几个数据会被搬移三次，我们可以先记录下已经删除的数据。每次的删除操作并不是真正地搬移数据，只是记录数据已经被删除。当数组没有更多空间存储数据时，我们再触发执行一次真正的删除操作，这样就大大减少了删除操作导致的数据搬移。其实这个就是JVM 标记清除垃圾回收算法的核心思想。

以java为例，ArrayList 最大的优势就是可以将很多数组操作的细节封装起来。比如前面提到的数组插入、删除数据时需要搬移其他数据等。另外，它还有一个优势，就是支持动态扩容。

数组本身在定义的时候需要预先指定大小，因为需要分配连续的内存空间。如果我们申请了大小为 10 的数组，当第 11 个数据需要存储到数组中时，我们就需要重新分配一块更大的空间，将原来的数据复制过去，然后再将新的数据插入。

如果使用 ArrayList，我们就完全不需要关心底层的扩容逻辑，ArrayList 已经帮我们实现好了。每次存储空间不够的时候，它都会将空间自动扩容为 1.5 倍大小。不过，这里需要注意一点，因为扩容操作涉及内存申请和数据搬移，是比较耗时的。所以，如果事先能确定需要存储的数据大小，最好在创建 ArrayList 的时候事先指定数据大小。如果不指定数据大小，默认构造一个初始容量为10的空列表。

此处如果没有事先指定数据大小，则会频繁的进行扩容的操作，是会比较消耗性能和提高时间复杂度的。

以下的场景比较适合使用数组

比如 int、long，需要封装为 Integer、Long 类，而 Autoboxing、Unboxing 则有一定的性能消耗，所以如果特别关注性能，或者希望使用基本类型，就可以选用数组。

总的来说数组是一种基本的数据结构，而平时使用的list等语言中的数据类型属于对其进行的封装，也称为容器，容器会帮助开发者自动实现一些功能去实现对数组的操作。

在平时工作中，对于业务开发，直接使用容器就足够了，省时省力。毕竟损耗一丢丢性能，完全不会影响到系统整体的性能。但如果你是做一些非常底层的开发，比如开发网络框架，性能的优化需要做到极致，这个时候数组就会优于容器，成为首选。

给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

* 作者：华星详谈 */ private static int deleteArrayDuplicates(int[] nums) { //思路：使用双指针的方式 //定义一个慢指针 int k = 0; //迭代循环快指针 for(int i=1;ia 时，买入股票 //当b prices[a]) { buying = prices[a]; isBuying = true; } //卖出 if (isBuying && prices[b] < prices[a]) { profit += prices[a] - buying; //清空数据 buying = 0; isBuying = false; } b++; } return profit; }

运行代码

习题2分析：

上述代码我们可以看到还存在很大的优化空间，下面给大家带来一种优化后的代码

时间复杂度：O(n)。其中 n 为数组的长度。我们只需要遍历一次数组即可。

空间复杂度：O(1)。只需要常数空间存放若干变量。

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。

说明:

示例 1:

示例 2:

习题3方式一：使用最简单的方法，直接旋转

* 作者：华星详谈 * * @param nums * @param k */ public static void rotate1(int[] nums, int k) { //temp:临时存储，previous：之前的值 int temp, previous; for (int i = 0; i < k; i++) { //保存数组最后一个元素 previous = nums[nums.length-1]; for (int j = 0; j < nums.length; j++) { //把当前位的值先暂时放入temp中 temp = nums[j]; //当前位的值替换为最后位的值 nums[j] = previous; //把当前位的值最为下一次循环的最后位值 previous = temp; } } System.out.println("方式一 直接旋转：nums = " + JSON.toJSONString(nums)); }

运行代码

习题3方式一 复杂度分析

时间复杂度：O(n * k)。两个循环体，循环次数不同，故是O(n * k)。

空间复杂度：O(1)。常数位的空间复杂度，没有额外的空间被使用。

习题3方式二：反转数组

这个方法基于这个事实：当我们旋转数组 k 次，k%n 个尾部元素会被移动到头部，剩下的元素会被向后移动。

在这个方法中，我们首先将所有元素反转。然后反转前 k 个元素，再反转后面 n-k 个元素，就能得到想要的结果。

假设 n=7 且 k=3。

* 作者：华星详谈 * * @param nums * @param k */ public static void rotate2(int[] nums, int k) { // k = k%数组的长度，eg k=3%7=3； k %= nums.length; //反转所有数字 reversal(nums, 0, nums.length - 1); //反转前 k 个数字 reversal(nums, 0, k - 1); //反转后 n-k 个数字 reversal(nums, k, nums.length - 1); System.out.println("方式二 使用反转：nums = " + JSON.toJSONString(nums)); } /** * 反转数组 * * @param nums * @param start 数组开始下标 * @param end 数组结束下标 */ private static void reversal(int[] nums, int start, int end) { while (start < end) { int temp = nums[start]; nums[start] = nums[end]; nums[end] = temp; start++; end--; } }

运行代码

习题3方式2 复杂度分析

给定一个整数数组，判断是否存在重复元素。

如果任意一值在数组中出现至少两次，函数返回 true。如果数组中每个元素都不相同，则返回 false 。

示例 1:输入: [1,2,3,1] 输出: true

示例 2:输入: [1,2,3,4] 输出: false

示例3:输入: [1,1,1,3,3,4,3,2,4,2] 输出: true

习题4方式一： 使用set集合的方式

习题4方式一 复杂度分析

该方式多创建了一个Set集合空间，会有一些额外的开销。

习题4方式二：排序之后判断相邻元素的是否相等

给定两个数组，编写一个函数来计算它们的交集。

示例 1： 输入：nums1 = [1,2,2,1], nums2 = [2,2] 输出：[2,2]

示例 2： 输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4] 输出：[4,9]

说明： 输出结果中每个元素出现的次数，应与元素在两个数组中出现次数的最小值一致。 我们可以不考虑输出结果的顺序。

进阶： 如果给定的数组已经排好序呢？你将如何优化你的算法？ 如果 nums1 的大小比 nums2 小很多，哪种方法更优？ 如果 nums2 的元素存储在磁盘上，内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？

习题6方式一：使用Java8 新特性

* 作者：华星详谈 * * @param nums1 * @param nums2 * @return */ public int[] intersect(int[] nums1, int[] nums2) { List list1 = Arrays.stream(nums1).sorted().boxed().collect(Collectors.toList()); List list2 = Arrays.stream(nums2).sorted().boxed().collect(Collectors.toList()); List collect = list1.stream().filter(num -> list2.contains(num)).collect(Collectors.toList()); return collect.stream().mapToInt(Integer::valueOf).toArray(); }

习题6方式二：使用哈希表

* 作者：华星详谈 * * @param nums1 长度较短的数组 * @param nums2 长度较长的数组 * @return */ public static int[] intersect(int[] nums1, int[] nums2) { //为了使算法最优化，在最外层迭代数组长度较长的那个 if (nums1.length > nums2.length) { return intersect(nums2, nums1); } //int[] result = new int[nums2.length]; Set set = new HashSet(); for (int num : nums2) { for (int i : nums1) { if (num == i) { set.add(i); } } } return set.stream().mapToInt(Integer::valueOf).toArray(); }

在上面的代码中，我们使用了双重for循环，这样会增加代码的时间复杂度，我们可以对以上的代码再次进行优化。

习题6方式二：使用哈希表（优化版）

* 作者：华星详谈 * * @param nums1 长度较短的数组 * @param nums2 长度较长的数组 * @return */ public static int[] intersect3(int[] nums1, int[] nums2) { //为了使算法最优化，在最外层迭代数组长度较长的那个 if (nums1.length > nums2.length) { return intersect3(nums2, nums1); } //定义一个map，存放每个元素出现的次数 Map map = new HashMap(); for (int num : nums2) { int count = map.getOrDefault(num, 0) + 1; map.put(num, count); } int index = 0; int[] result = new int[nums1.length]; for (int num : nums1) { int count = map.getOrDefault(num, 0); if (count > 0) { //说明该元素存在于num1、num2中 result[index++] = num; //该元素已经放入result，自身减一 count--; if (count > 0) { map.put(num, count); } else { map.remove(num); } } } //返回index长度的排序集合 return Arrays.copyOfRange(result, 0, index); }

习题6方式三：使用排序后双指针的方式，(当num2长度过大，内存放不下是不适用) ps:执行时间耗时最少

解题思路:

* 作者：华星详谈 * * @param nums1 长度较短的数组 * @param nums2 长度较长的数组 * @return */ public static int[] intersect4(int[] nums1, int[] nums2) { //为了使算法最优化，在最外层迭代数组长度较长的那个 if (nums1.length > nums2.length) { return intersect4(nums2, nums1); } Arrays.sort(nums1); Arrays.sort(nums2); int length1 = nums1.length, length2 = nums2.length; int index = 0, index1 = 0, index2 = 0; int[] result = new int[Math.min(length1, length2)]; //当两个索引都比长度小时，才进入循环 while (index1 < length1 && index2 < length2) { //元素较小的右移一位 if (nums1[index1] < nums2[index2]) { index1++; } else if (nums1[index1] > nums2[index2]) { index2++; } else { result[index++] = nums1[index1]; index1++; index2++; } } return Arrays.copyOfRange(result, 0, index); } 习题7、加一

给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外，这个整数不会以零开头。

示例 1：输入：digits = [1,2,3] 输出：[1,2,4] 解释：输入数组表示数字 123。

示例 2：输入：digits = [4,3,2,1]输出：[4,3,2,2] 解释：输入数组表示数字 4321。

示例 3：输入：digits = [0]输出：[1]

提示：

步骤：

* 作者：华星详谈 * * @return */ public boolean isValidSudoku(char[][] board) { int[][] hang = new int[9][9];//row int[][] lie = new int[9][9];//colomn int[][] gezi = new int[9][9];//9-digit cell for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { int x = board[i][j] - '0'; if (x >= 1 && x 1 || lie[j][x - 1] > 1 || gezi[i / 3 * 3 + j / 3][x - 1] > 1) { return false; } } } } return true; } 本文涉及到的文章

CSDN 博客专栏：https://blog.csdn.net/a767815662/category_10659228.html

文中代码 Git 地址： https://github.com/17666555910/KeyGenMe

微信公共号：【华星详谈】 https://mp.weixin.qq.com/mp/appmsgalbum?__biz=MzI0MTY3Mjg5MQ==&action=getalbum&album_id=1648889604197924868&scene=173&from_msgid=2247484074&from_itemidx=1&count=3&uin=&key=&devicetype=Windows+10+x64&version=63010043&lang=zh_CN&ascene=1&session_us=gh_4e3c48fa7525&fontgear=2