一、题目

给定两个数组,编写一个函数来计算它们的交集。
示例 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 的元素存储在磁盘上,磁盘内存是有限的,并且你不能一次加载所有的元素到内存中,你该怎么办?

二、解决方案

方案一:哈希映射

(暂不实现)
这里,我们需要使用 HashMap 来跟踪每个数字出现的次数。
我们先在 HashMap 中记录一个数组中的存在的数字和对应出现的次数。然后遍历第二个数组,检查数字在 HashMap 中是否存在,如果存在且计数为正,则将该数字添加到答案并减少 HashMap 中的计数。

检查数组的大小并对较小的数组进行哈希映射是一个小细节,当其中一个数组较大时,会减少内存的使用。

算法:

  • 如果 nums1 元素个数大于 nums2,则交换数组元素。
  • 对于 nums1 的每个元素,添加到 HashMap m 中,如果元素已经存在则增加对应的计数。
  • 初始化 k = 0,记录当前交集元素个数。
  • 遍历数组 nums2:
    • 检查元素在 m 中是否存在,若存在且计数为正:
      • 将元素拷贝到 nums1[k],且 k++。
      • 减少 m 中对应元素的计数。
  • 返回 nums1 前 k 个元素。

复杂度分析:

  • 时间复杂度:O(n+m)\mathcal{O}(n + m)。其中 n,m 分别代表了数组的大小。
  • 空间复杂度:O(min(n,m))\mathcal{O}(\min(n, m)),我们对较小的数组进行哈希映射使用的空间。

方案二:排序

当输入数据是有序的,推荐使用此方法。在这里,我们对两个数组进行排序,并且使用两个指针在一次扫描后找出公共的数字。

算法:

  • 对数组 nums1 和 nums2 排序。
  • 初始化指针 i,j 和 k 为 0。
  • 指针 i 指向 nums1,指针 j 指向 nums2:
    • 如果 nums1[i] < nums2[j],则 i++。
    • 如果 nums1[i] > nums2[j],则 j++。
    • 如果 nums1[i] == nums2[j],将元素拷贝到 nums1[k],且 i++,j++,k++。
  • 返回数组 nums1 前 k 个元素。

我的代码如下(通过):

int cmpfunc(const void* a, const void* b)
{
    if (*(int*)a > *(int*)b) 
        return 1;
    else if (*(int*)a < *(int*)b) 
        return -1;
    else if (*(int*)a == *(int*)b) 
        return 0;
    return 0;
}

int* intersect(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) 
{
    // first: sort the two array
    qsort(nums1, nums1Size, sizeof(nums1[0]), cmpfunc);
    qsort(nums2, nums2Size, sizeof(nums2[0]), cmpfunc);
 
    int len = 0;
    for (int i = 0, j = 0; i < nums1Size && j < nums2Size; )
    {
        if (nums1[i] < nums2[j])
            i++;
        else if (nums1[i] > nums2[j])
            j++;
        else
        {
            nums1[len++] = nums1[i++];
            j++;
        }
    }
    *returnSize = len;
    int* arr = (int*)malloc(sizeof(int) * len);
    if (!arr)
    {
        printf("fail to malloc!");
        return NULL;
    }
    for (int i = 0; i < len; i++)
    {
        arr[i] = nums1[i];
    }
    return arr;
}

复杂度分析:

  • 时间复杂度:O(nlogn+mlogm)\mathcal{O}(n\log{n} + m\log{m})。其中 n,m 分别代表了数组的大小。我们对数组进行了排序然后进行了线性扫描。
  • 空间复杂度:O(1)O(1),我们忽略存储答案所使用的空间,因为它对算法本身并不重要。