题目

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

示例 1：

输入：nums1 = [1,2,2,1], nums2 = [2,2]

输出：[2,2]

示例 2:

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

标签

哈希表；排序；数组；双指针

解题思路

方法一：哈希表

  • 由于同一个数字在两个数组中都可能出现多次，因此可以用哈希表存储每个数字出现的次数。对于一个数字，其在交集中出现的次数等于该数字在两个数组中出现次数的最小值。
  • 首先遍历第一个数组，并在哈希表中记录第一个数组中的每个数字以及对应出现的次数，然后遍历第二个数组，对于第二个数组中的每个数字，如果在哈希表中存在这个数字，则将该数字添加到答案，并减少哈希表中该数字出现的次数。

  • 为了降低空间复杂度，首先遍历较短的数组并在哈希表中记录每个数字以及对应出现的次数，然后遍历较长的数组得到交集。

    方法二：排序

  • 如果两个数组是有序的，则可以便捷地计算两个数组的交集。

  • 首先对两个数组进行排序，然后使用两个指针遍历两个数组。

  • 初始时，两个指针分别指向两个数组的头部。每次比较两个指针指向的两个数组中的数字，如果两个数字不相等，则将指向较小数字的指针右移一位，如果两个数字相等，将该数字添加到答案，并将两个指针都右移一位。当至少有一个指针超出数组范围时，遍历结束。

    代码

    1. //给定两个数组，编写一个函数来计算它们的交集。
    2. public class Leetcode350 {
    3.   public static void main(String[] args) {
    4.       int[] nums1 = {1, 2, 2, 1};
    5.       int[] nums2 = {2};
    6.       int[] result = Leetcode350.intersect2(nums1, nums2);
    7.       for (int i = 0; i < result.length; i++) {
    8.           System.out.print(result[i] + " ");
    9.       }
    10.   }
    12.   public static int[] intersect(int[] nums1, int[] nums2) {
    13.       //方法一：哈希表
    14.       //先比较nums1与nums2的数组大小，将较小的作为参照对象，减少空间复杂度
    15.       if (nums1.length > nums2.length) {
    16.           return intersect(nums2, nums1);
    17.       }
    18.       //建立哈希映射，将元素与次数进行对应
    19.       Map<Integer, Integer> map = new HashMap<>();
    20.       //遍历较短的数组，统计每个元素出现的次数
    21.       for (int num : nums1) {
    22.           //刚开始键值对为null,count记录每个元素出现的次数
    23.           //getOrDefault:如果get(num)为空，则返回defaultValue，否则返回get(num)
    24.           int count = map.getOrDefault(num, 0) + 1;
    25.           map.put(num, count);
    26.       }
    27.       int[] result = new int[nums1.length]; //定义结果数组
    28.       int index = 0; //结果数组索引
    29.       //遍历较长的数组，进行比较
    30.       for (int num : nums2) {
    31.           //取较长数组的元素个数
    32.           int count = map.getOrDefault(num, 0);
    33.           //判断count是否大于0
    34.           if (count > 0) {
    35.               result[index++] = num;
    36.               count--;
    37.               if (count > 0) {
    38.                   map.put(num, count);
    39.               } else {
    40.                   map.remove(num);
    41.               }
    42.           }
    43.       }
    44.       return Arrays.copyOfRange(result, 0, index);
    45.   }
    47.   public static int[] intersect2(int[] nums1, int[] nums2) {
    48.       //方法二：排序
    49.       //先比较nums1与nums2的数组大小，将较小的作为参照对象，减少空间复杂度
    50.       if (nums1.length > nums2.length) {
    51.           return intersect2(nums2, nums1);
    52.       }
    53.       //排序
    54.       Arrays.sort(nums1);
    55.       Arrays.sort(nums2);
    56.       //定义结果数组及索引
    57.       int[] result = new int[nums1.length];
    58.       int index = 0;
    59.       //核心功能：双指针定位比较
    60.       for (int i = 0, j = 0; i < nums1.length && j < nums2.length; ) {
    61.           if (nums1[i] < nums2[j]) {
    62.               i++;
    63.           } else if (nums1[i] == nums2[j]) {
    64.               result[index++] = nums1[i];
    65.               i++;
    66.               j++;
    67.           } else {
    68.               j++;
    69.           }
    70.       }
    71.       return Arrays.copyOfRange(result, 0, index);
    73.   }
    74. }

    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/intersection-of-two-arrays-ii