数组概念

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

为什么大多数编程语言中，数组要从 0 开始编号，而不是从 1 开始呢？

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

  1. a[k]_address = base_address + k * type_size

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

  1. a[k]_address = base_address + (k-1)*type_size

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

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

数组是如何实现根据下标随机访问数组元素?

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

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

  1. a[i]_address = base_address + i * data_type_size

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

问数组和链表的区别?

  • 链表适合插入、删除，时间复杂度 O(1)；
  • 数组是适合查找操作，支持随机访问，根据下标随机访问的时间复杂度为 O(1);

插入操作的时间复杂度分析

假设数组的长度为 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的空列表。

  1. List<User> users = new ArrayList(10000);
  2. for (int i = 0; i < 10000; ++i) {
  3.   users.add(xxx);
  4. }

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

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

  • 1.Java ArrayList 无法存储基本类型

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

  • 2.如果数据大小事先已知，并且对数据的操作非常简单，用不到 ArrayList 提供的大部分方法，也可以直接使用数组。

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

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

数组习题:

1、删除排序数组中的重复项

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

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

代码片段

  1. /**
  2.      * 删除排序数组中的重复项
  3.      * 给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
  4.      * 不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
  5.      * <p>
  6.      * 作者：华星详谈
  7.      */
  8.     private static int deleteArrayDuplicates(int[] nums) {
  9.         //思路：使用双指针的方式
  10.         //定义一个慢指针
  11.         int k = 0;
  12.         //迭代循环快指针
  13.         for(int i=1;i<nums.length;i++){
  14.             //如果快指针的值和慢指针的值不相等则说明为不重复的,则把值写入慢指针对应的数组元素中去
  15.             if(nums[i] != nums[k]){
  16.                 k++;
  17.                 nums[k]=nums[i];
  18.             }
  19.         }
  20.         //移动慢指针
  21.         return k+1;
  22.     }

运行代码

  1.     public static void main(String[] args) {
  2.         //---------------- 习题1:删除排序数组中的重复项 begin -----------------------------
  3.         /**
  4.          * 删除排序数组中的重复项
  5.          * 示例 1:给定数组 nums = [1,1,2],函数应该返回新的长度 2,
  6.          *       并且原数组 nums 的前两个元素被修改为 1, 2。你不需要考虑数组中超出新长度后面的元素。
  7.          * 示例 2:给定 nums = [0,0,1,1,1,2,2,3,3,4],
  8.          *       函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。你不需要考虑数组中超出新长度后面的元素。
  9.          */
  10.         int[] nums = {1, 1, 2};
  11.         int length = deleteArrayDuplicates(nums);
  12.         System.out.println("习题1:新的数组长度为 = " + length);
  13.         System.out.println("习题1:删除排序数组中的重复项: " + JSONObject.toJSONString(Arrays.copyOfRange(nums, 0, length)));
  14.         //----------------- 习题1:删除排序数组中的重复项 end ------------------------------
  15.     }

习题1分析：

  • 时间复杂度：O(n)。n为数组长度
  • 空间复杂度：O(1)。没有创建额外的空间

2、买卖股票的最佳时机

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1: 输入: [7,1,5,3,6,4] 输出: 7

  1. 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3

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

  1. 解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。

示例 3:输入: [7,6,4,3,1] 输出: 0

  1. 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

注意： 你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。 因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

Java代码

  1. /**
  2.      * TODO 买卖股票的最佳时机
  3.      * 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
  4.      * 设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
  5.      * 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
  6.      * <p>
  7.      * 作者：华星详谈
  8.      *
  9.      * @param prices
  10.      * @return
  11.      */
  12.     public static int maxProfit(int[] prices) {
  13.         //解题思路：使用双指针，a为当前指针，b为下一个指针。
  14.         //当b>a 时，买入股票
  15.         //当b<a时，卖出股票，利润=arr[a]-买入时的价格
  16.         //下一个指针
  17.         int b = 1;
  18.         //利润
  19.         int profit = 0;
  20.         //买入时的价格
  21.         int buying = 0;
  22.         //是否有买入
  23.         boolean isBuying = false;
  24.         for (int a = 0; a < prices.length; a++) {
  25.             if (a == prices.length - 1) {
  26.                 if (isBuying) {
  27.                     profit += prices[a] - buying;
  28.                 }
  29.                 break;
  30.             }
  31.             //买入
  32.             if (!isBuying && prices[b] > prices[a]) {
  33.                 buying = prices[a];
  34.                 isBuying = true;
  35.             }
  36.             //卖出
  37.             if (isBuying && prices[b] < prices[a]) {
  38.                 profit += prices[a] - buying;
  39.                 //清空数据
  40.                 buying = 0;
  41.                 isBuying = false;
  42.             }
  43.             b++;
  44.         }
  45.         return profit;
  46.     }

运行代码

  1. int[] nums2 = {7, 1, 5, 3, 6, 4};
  2. System.out.println("习题2:买卖股票的最佳时机: " + ArrayAlgorithmToPractice.maxProfit(nums));

习题2分析：

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

  1.     public static int maxProfit2(int[] prices) {
  2.         //利润
  3.         int profit = 0;
  4.         for (int i = 1; i < prices.length; i++) {
  5.             //获取利润，当prices[i] - prices[i-1] > 0  时，说明有利可图
  6.             profit += Math.max(0, prices[i] - prices[i - 1]);
  7.         }
  8.         return profit;
  9.     }
  • 时间复杂度：O(n)。其中 n 为数组的长度。我们只需要遍历一次数组即可。
  • 空间复杂度：O(1)。只需要常数空间存放若干变量。

习题3、旋转数组

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

说明:

  • 尽可能想出更多的解决方案。
  • 要求使用空间复杂度为 O(1) 的 原地 算法。

示例 1:

  1. 输入: nums = [1,2,3,4,5,6,7], k = 3
  2. 输出: [5,6,7,1,2,3,4]
  3. 解释:
  4. 向右旋转 1 步: [7,1,2,3,4,5,6]
  5. 向右旋转 2 步: [6,7,1,2,3,4,5]
  6. 向右旋转 3 步: [5,6,7,1,2,3,4]

示例 2:

  1. 输入：nums = [-1,-100,3,99], k = 2
  2. 输出：[3,99,-1,-100]
  3. 解释: 
  4. 向右旋转 1 步: [99,-1,-100,3]
  5. 向右旋转 2 步: [3,99,-1,-100]

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

  1. /**
  2.      * TODO 旋转数组    方式1：直接旋转
  3.      * 给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
  4.      * 说明:
  5.      * 尽可能想出更多的解决方案。
  6.      * 要求使用空间复杂度为 O(1) 的 原地 算法。
  7.      * <p>
  8.      * 作者：华星详谈
  9.      *
  10.      * @param nums
  11.      * @param k
  12.      */
  13.     public static void rotate1(int[] nums, int k) {
  14.         //temp:临时存储，previous：之前的值
  15.         int temp, previous;
  16.         for (int i = 0; i < k; i++) {
  17.             //保存数组最后一个元素
  18.             previous = nums[nums.length-1];
  19.             for (int j = 0; j < nums.length; j++) {
  20.                 //把当前位的值先暂时放入temp中
  21.                 temp = nums[j];
  22.                 //当前位的值替换为最后位的值
  23.                 nums[j] = previous;
  24.                 //把当前位的值最为下一次循环的最后位值
  25.                 previous = temp;
  26.             }
  27.         }
  28.         System.out.println("方式一 直接旋转：nums = " + JSON.toJSONString(nums));
  29.     }

运行代码

  1. //方式1：直接旋转
  2. nums = new int[]{1, 2, 3, 4, 5, 6, 7};
  3. ArrayAlgorithmToPractice.rotate1(nums,3);

习题3方式一 复杂度分析

  • 时间复杂度：O(n k)。两个循环体，循环次数不同，故是O(n k)。
  • 空间复杂度：O(1)。常数位的空间复杂度，没有额外的空间被使用。

习题3方式二：反转数组

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

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

假设 n=7 且 k=3。

  1. 原始数组                  : 1 2 3 4 5 6 7
  2. 反转所有数字后             : 7 6 5 4 3 2 1
  3. 反转前 k 个数字后          : 5 6 7 4 3 2 1
  4. 反转后 n-k 个数字后        : 5 6 7 1 2 3 4 --> 结果
  1. /**
  2.      * TODO 旋转数组    方式2：反转数组
  3.      * 给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
  4.      * 说明:
  5.      * 尽可能想出更多的解决方案。
  6.      * 要求使用空间复杂度为 O(1) 的 原地 算法。
  7.      * <p>
  8.      * 作者：华星详谈
  9.      *
  10.      * @param nums
  11.      * @param k
  12.      */
  13.     public static void rotate2(int[] nums, int k) {
  14.         // k = k%数组的长度，eg k=3%7=3；
  15.         k %= nums.length;
  16.         //反转所有数字
  17.         reversal(nums, 0, nums.length - 1);
  18.         //反转前 k 个数字
  19.         reversal(nums, 0, k - 1);
  20.         //反转后 n-k 个数字
  21.         reversal(nums, k, nums.length - 1);
  22.         System.out.println("方式二 使用反转：nums = " + JSON.toJSONString(nums));
  23.     }
  25.     /**
  26.      * 反转数组
  27.      *
  28.      * @param nums
  29.      * @param start 数组开始下标
  30.      * @param end   数组结束下标
  31.      */
  32.     private static void reversal(int[] nums, int start, int end) {
  33.         while (start < end) {
  34.             int temp = nums[start];
  35.             nums[start] = nums[end];
  36.             nums[end] = temp;
  37.             start++;
  38.             end--;
  39.         }
  40.     }

运行代码

  1. //方式2：
  2. nums = new int[]{1, 2, 3, 4, 5, 6, 7};
  3. ArrayAlgorithmToPractice.rotate2(nums, 3);

习题3方式2 复杂度分析

  • 时间复杂度：O(n)。n为数组的元素。n 个元素被反转了总共 3 次。
  • 空间复杂度：O(1)。常数位的空间复杂度，没有额外的空间被使用

习题4：存在重复元素

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

如果任意一值在数组中出现至少两次，函数返回 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集合的方式

  1.     /**
  2.      * TODO 存在重复元素  方式1：使用set集合的方式
  3.      * 给定一个整数数组，判断是否存在重复元素。
  4.      * 如果任意一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。
  5.      *
  6.      * 作者：华星详谈
  7.      * @param nums
  8.      * @return
  9.      */
  10.     public static boolean containsDuplicate(int[] nums) {
  11.         Set<Integer> set = new HashSet();
  12.         for(int i=0;i < nums.length;i++){
  13.             if(!set.add(nums[i])){
  14.                 return true;
  15.             }
  16.         }
  17.         return false;
  18.     }

习题4方式一 复杂度分析

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

  • 时间复杂度: O(N)，其中 N 为数组的长度;
  • 空间复杂度：O(N)，额外创建了set集合，n为set集合的长度。

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

  1.    /**
  2.      * TODO 存在重复元素  方式2：排序之后判断相邻元素的是否相等
  3.      * 给定一个整数数组，判断是否存在重复元素。
  4.      * 如果任意一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。
  5.      *
  6.      * 作者：华星详谈
  7.      * @param nums
  8.      * @return
  9.      */
  10.     public static boolean containsDuplicate2(int[] nums) {
  11.         Arrays.sort(nums);
  12.         for(int i=1;i <nums.length;i++){
  13.             if(nums[i-1] == nums[i]){
  14.                 return true;
  15.             }
  16.         }
  17.         return false;
  18.     }

习题4方式二 复杂度分析

该方法在对数组进行排序之后直接判断相邻两个元素是否相等，若相等则说明有相同的元素。

  • 时间复杂度：O(N log N)，其中 N 为数组的长度。需要对数组进行排序。
  • 空间复杂度：O(log n)。

习题4方式二优化版

  1.     public static boolean containsDuplicate3(int[] nums) {
  2.         return IntStream.of(nums).distinct().count() != nums.length;
  3.     }

核心是使用Java8 的新特性之IntStream流。通过distinct()方法去重，count()汇总总数和数组的长度进行比较。其时间复杂度和空间复杂度与都为O(n)。

习题5：只出现一次的数字

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

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

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

习题5方式一：使用hashSet集合方式

  1.     /**
  2.      * TODO 只出现一次的数字   方式一：使用hashSet集合方式
  3.      * 说明：
  4.      * 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
  5.      * <p>
  6.      * 作者：华星详谈
  7.      * @param nums
  8.      * @return
  9.      */
  10.     public static int singleNumber(int[] nums) {
  11.         Set<Integer> set = new HashSet<>();
  12.         for (int num : nums) {
  13.             if (!set.add(num)) {
  14.                 //添加不成功，则说明是重复的数据，则删除对应的元素
  15.                 set.remove(num);
  16.             }
  17.         }
  18.         return set.isEmpty() ? -1 : set.iterator().next();
  19.     }

习题5方式一 复杂度分析

  • 时间复杂度：O(n)
  • 空间复杂度：O(n²)

习题5方式二：使用Java8 新特性-分组取list长度为1

  1.  /**
  2.      * TODO 只出现一次的数字   方式二：分组取list长度为1
  3.      * 说明：
  4.      * 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
  5.      * <p>
  6.      * 作者：华星详谈
  7.      * @param nums
  8.      * @return
  9.      */
  10.     public static int singleNumber2(int[] nums) {
  11.         List<Integer> list = Arrays.stream(nums).boxed()
  12.                 .collect(Collectors.groupingBy(value -> value))
  13.                 .entrySet()
  14.                 .stream()
  15.                 .filter(i -> i.getValue().size() == 1)
  16.                 .map(Map.Entry::getKey)
  17.                 .collect(Collectors.toList());
  18.         return list.isEmpty() ? -1 : list.get(0);
  19.     }

习题6.两个数组的交集

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

示例 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 新特性

  1.      * TODO 两个数组的交集     方式一：使用Java8新特性
  2.      * 说明：
  3.      * 输出结果中每个元素出现的次数，应与元素在两个数组中出现次数的最小值一致。
  4.      * 我们可以不考虑输出结果的顺序。
  5.      * <p>
  6.      * 作者：华星详谈
  7.      *
  8.      * @param nums1
  9.      * @param nums2
  10.      * @return
  11.      */
  12.     public int[] intersect(int[] nums1, int[] nums2) {
  13.         List<Integer> list1 = Arrays.stream(nums1).sorted().boxed().collect(Collectors.toList());
  14.         List<Integer> list2 = Arrays.stream(nums2).sorted().boxed().collect(Collectors.toList());
  15.         List<Integer> collect = list1.stream().filter(num -> list2.contains(num)).collect(Collectors.toList());
  16.         return collect.stream().mapToInt(Integer::valueOf).toArray();
  17.     }

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

  1.      * TODO 两个数组的交集     方式二：使用hash表的方式
  2.      * 说明：
  3.      * 输出结果中每个元素出现的次数，应与元素在两个数组中出现次数的最小值一致。
  4.      * 我们可以不考虑输出结果的顺序。
  5.      * <p>
  6.      * 作者：华星详谈
  7.      *
  8.      * @param nums1 长度较短的数组
  9.      * @param nums2 长度较长的数组
  10.      * @return
  11.      */
  12.     public static int[] intersect(int[] nums1, int[] nums2) {
  13.         //为了使算法最优化，在最外层迭代数组长度较长的那个
  14.         if (nums1.length > nums2.length) {
  15.             return intersect(nums2, nums1);
  16.         }
  17.         //int[] result = new int[nums2.length];
  18.         Set<Integer> set = new HashSet();
  19.         for (int num : nums2) {
  20.             for (int i : nums1) {
  21.                 if (num == i) {
  22.                     set.add(i);
  23.                 }
  24.             }
  25.         }
  26.         return set.stream().mapToInt(Integer::valueOf).toArray();
  27.     }

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

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

  1. /**
  2.      * TODO 两个数组的交集     方式二：使用hash表的方式(优化版)
  3.      * 说明：
  4.      * 输出结果中每个元素出现的次数，应与元素在两个数组中出现次数的最小值一致。
  5.      * 我们可以不考虑输出结果的顺序。
  6.      * <p>
  7.      * 作者：华星详谈
  8.      *
  9.      * @param nums1 长度较短的数组
  10.      * @param nums2 长度较长的数组
  11.      * @return
  12.      */
  13.     public static int[] intersect3(int[] nums1, int[] nums2) {
  14.         //为了使算法最优化，在最外层迭代数组长度较长的那个
  15.         if (nums1.length > nums2.length) {
  16.             return intersect3(nums2, nums1);
  17.         }
  18.         //定义一个map，存放每个元素出现的次数
  19.         Map<Integer, Integer> map = new HashMap<>();
  20.         for (int num : nums2) {
  21.             int count = map.getOrDefault(num, 0) + 1;
  22.             map.put(num, count);
  23.         }
  25.         int index = 0;
  26.         int[] result = new int[nums1.length];
  27.         for (int num : nums1) {
  28.             int count = map.getOrDefault(num, 0);
  29.             if (count > 0) {
  30.                 //说明该元素存在于num1、num2中
  31.                 result[index++] = num;
  32.                 //该元素已经放入result，自身减一
  33.                 count--;
  34.                 if (count > 0) {
  35.                     map.put(num, count);
  36.                 } else {
  37.                     map.remove(num);
  38.                 }
  39.             }
  40.         }
  41.         //返回index长度的排序集合
  42.         return Arrays.copyOfRange(result, 0, index);
  43.     }

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

解题思路:

1：先对数组进行排序
2：比较数组长度进行迭代，当两个索引都比长度小时，才进入循环
3：如果nums1[index1]、nums2[index2] 相等，则说明元素存在于num1和num2中，把该元素存放在新的数组中
4：如果nums1[index1]> nums2[index2]，index2++；
5：如果nums1[index1]< nums2[index2]，index1++；

/**
     * TODO 两个数组的交集     方式三：使用排序后双指针的方式，(当num2长度过大，内存放不下是不适用) ps:执行时间耗时最少
     * 说明：
     * 输出结果中每个元素出现的次数，应与元素在两个数组中出现次数的最小值一致。
     * 我们可以不考虑输出结果的顺序。
     * <p>
     * 作者：华星详谈
     *
     * @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]

提示：

  • 1 <= digits.length <= 100
  • 0 <= digits[i] <= 9

习题7方式一：

解题思路:

判断digits.length 是否为9 如果为9就改为1，继续循环digits.length-1，若为不等于9，则+1。最后处理特殊情况 99。

    /**
     * TODO 加一  解题思路：判断digits.length 是否为9 如果为9就改为1，继续循环digits.length-1，若为不等于9，则+1。最后处理特殊情况 99。
     * 说明：
     * 输出结果中每个元素出现的次数，应与元素在两个数组中出现次数的最小值一致。
     * 我们可以不考虑输出结果的顺序。
     * <p>
     * 作者：华星详谈
     *
     * @param digits
     * @return
     */
    public static int[] plusOne(int[] digits) {
        //解题思路：判断digits.length 是否为9 如果为9就改为1，继续循环digits.length-1，若为不等于9，则+1。最后处理特殊情况 99。
        for (int i = digits.length - 1; i >= 0; i--) {
            if (digits[i] == 9) {
                digits[i] = 0;
            } else {
                digits[i]++;
                return digits;
            }
        }
        //处理最高位为9的情况
        int[] result = new int[digits.length + 1];
        result[0] = 1;
        return result;
    }

习题7 方式二：digits[i]++ ,然后 digits[i] 取余 10，如果能够被整除，说明进一位，如果不能够被整除则直接返回

    /**
     * TODO 加一  解题思路：digits[i]++ ,然后 digits[i] 取余 10，如果能够被整除，说明进一位，如果不能够被整除则直接返回
     * 说明：
     * 输出结果中每个元素出现的次数，应与元素在两个数组中出现次数的最小值一致。
     * 我们可以不考虑输出结果的顺序。
     * <p>
     * 作者：华星详谈
     *
     * @param digits
     * @return
     */
    public static int[] plusOne2(int[] digits) {
        //解题思路：digits[i]++ ,然后 digits[i] 取余 10，如果能够被整除，说明进一位，如果不能够被整除则直接返回
        for (int i = digits.length - 1; i >= 0; i--) {
            digits[i]++;
            digits[i] %= 10;
            if (digits[i] != 0) {
                //说明不能够整除
                return digits;
            }
        }
        //处理特殊情况：最高位为9时
        int[] result = new int[digits.length + 1];
        result[0] = 1;
        return result;
    }

习题8 移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

示例: 输入: [0,1,0,3,12] 输出: [1,3,12,0,0]

说明:

必须在原数组上操作，不能拷贝额外的数组。
尽量减少操作次数。

习题8 解题步骤

解题思路：

使用双指针的模式，定义 left 和 right 指针。

  1. 当 nums[left] 等于0时，移动left指针；
  2. 当 nums[left] 不等于0时，分两种情况
    • left 指针大于right时，说明前一次循环中的元素为0，故进行元素替换。移动 left、right 指针。
    • left 指针小于等于right时，直接移动 left、right 指针。
    /**
     * TODO 移动零：使用双指针
     * 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
     * 说明:
     * 必须在原数组上操作，不能拷贝额外的数组。
     * 尽量减少操作次数。
     * <p>
     * 作者：华星详谈
     *
     * @return
     */
    public static void moveZeroes(int[] nums) {
        int left = 0, right = 0;
        while (left < nums.length) {
            if (nums[left] != 0) {
                if (left > right) {
                    nums[right] = nums[left];
                    nums[left] = 0;
                }
                right++;
            }
            left++;
        }
        System.out.println("习题8 移动零：使用双指针：" + JSONObject.toJSONString(nums));
    }

习题9 两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

你可以按任意顺序返回答案。

示例 1：输入：nums = [2,7,11,15], target = 9 输出：[0,1] 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：输入：nums = [3,2,4], target = 6 输出：[1,2]

示例 3：输入：nums = [3,3], target = 6 输出：[0,1]

习题9 方式一 使用数组的方式

解题思路

数组转list，判断target-当前元素的值在list中是否存在，若存在返回对应的下标，若不存在，进入下一个循环

   /**
     * TODO 两数之和：解题思路：数组转list，判断target-当前元素的值在list中是否存在，若存在返回对应的下标，若不存在，进入下一个循环
     * 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 的那 两个 整数，并返回它们的数组下标。
     * 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
     * 你可以按任意顺序返回答案。
     * <p>
     * 作者：华星详谈
     *
     * @return
     */
    public static int[] twoSum(int[] nums, int target) {
        //解题思路：数组转list，判断target-当前元素的值在list中是否存在，若存在返回对应的下标，若不存在，进入下一个循环
        List<Integer> list = Arrays.stream(nums).boxed().collect(Collectors.toList());
        int[] result = new int[nums.length];
        int index = 0;
        for (int i = 0; i < nums.length; i++) {
            int i1 = target - nums[i];
            if (list.contains(i1)) {
                if (list.indexOf(nums[i]) != list.lastIndexOf(i1)) {
                    result[0] = list.indexOf(nums[i]);
                    result[1] = list.lastIndexOf(i1);
                    index++;
                    break;
                }
            }
        }
        return Arrays.copyOfRange(result, 0, index + 1);
    }

习题9 方式二：使用hash表的方式

解题思路：使用hash表的方式

  1. 迭代数组，如果target-num[i] 不存在map中存在的话，把元素和下标添加到map中；
  2. 如果target-num[i] 存在map中，返回对应的下标；
    /**
     * TODO 两数之和：方式二(推荐使用)：解题思路：使用hash表的方式。定义一个map，存放元素和对应的下标，如果map中包含（target-当前元素），则返回他们的下标
     * 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 的那 两个 整数，并返回它们的数组下标。
     * 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
     * 你可以按任意顺序返回答案。
     * <p>
     * 作者：华星详谈
     *
     * @return
     */
    public static int[] twoSum2(int[] nums, int target) {
        //使用hash表的方式。定义一个map，存放元素和对应的下标，如果map中包含（target-当前元素），则返回他们的下标
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(target - nums[i])) {
                return new int[]{map.get(target - nums[i]), i};
            }
            map.put(nums[i], i);
        }
        return new int[0];
    }

习题10 有效的数独

判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。

  • 数字 1-9 在每一行只能出现一次。
  • 数字 1-9 在每一列只能出现一次。
  • 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

数独部分空格内已填入了数字，空白格用 ‘.’ 表示。

示例 1:

输入:
[
  ["5","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
]
输出: true

示例 2:

输入:
[
 ["8","3",".",".","7",".",".",".","."],
 ["6",".",".","1","9","5",".",".","."],
 [".","9","8",".",".",".",".","6","."],
 ["8",".",".",".","6",".",".",".","3"],
 ["4",".",".","8",".","3",".",".","1"],
 ["7",".",".",".","2",".",".",".","6"],
 [".","6",".",".",".",".","2","8","."],
 [".",".",".","4","1","9",".",".","5"],
 [".",".",".",".","8",".",".","7","9"]
]
输出: false
解释: 除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。
     但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。

说明:

  • 一个有效的数独（部分已被填充）不一定是可解的。
  • 只需要根据以上规则，验证已经填入的数字是否有效即可。
  • 给定数独序列只包含数字 1-9 和字符 ‘.’ 。
  • 给定数独永远是 9x9 形式的。

解题思路

1：如何枚举子数独？

可以使用 box_index = (row / 3) * 3 + columns / 3，其中 / 是整数除法。

如何确保行 / 列 / 子数独中没有重复项？

可以利用 value -> count 哈希映射来跟踪所有已经遇到的值。

步骤：

  • 遍历数独。
  • 检查看到每个单元格值是否已经在当前的行 / 列 / 子数独中出现过：
    • 如果出现重复，返回 false。
    • 如果没有，则保留此值以进行进一步跟踪。
  • 返回 true。
    /**
     * TODO 有效的数独
     * 判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。
     *
     * 数字 1-9 在每一行只能出现一次。
     * 数字 1-9 在每一列只能出现一次。
     * 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
     * 数独部分空格内已填入了数字，空白格用 '.' 表示。
     *
     * 说明:
     * 一个有效的数独（部分已被填充）不一定是可解的。
     * 只需要根据以上规则，验证已经填入的数字是否有效即可。
     * 给定数独序列只包含数字 1-9 和字符 '.' 。
     * 给定数独永远是 9x9 形式的。
     * <p>
     * 作者：华星详谈
     *
     * @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 <= 9) {
                    hang[i][x - 1]++;
                    lie[j][x - 1]++;
                    gezi[i / 3 * 3 + j / 3][x - 1]++;
                    if (hang[i][x - 1] > 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