[数组] 350两个数组的交集

题目

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

示例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 的元素存储在磁盘上，内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？

题解

C语言

方法一：

暴力破解法，选定一个数组，每次从中拿出一个数，然后遍历另一个数组看有没有相同的，有就加到输出数组中，并把第二个数组的该数置为一个数据一中没有的数，否则跳过这个数。依次遍历完数组一种的数即可。

int* intersect(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize){
    int* result;
    int min;
    if(nums1Size > nums2Size)
        min = nums2Size;
    else
        min = nums1Size;
    result = (int*)malloc(sizeof(int) * min);

    int k = 0;
    for(int i = 0; i < nums1Size; i++){
        for(int j = 0; j < nums2Size; j++){
            if(nums1[i] == nums2[j]){
                result[k] = nums1[i];
                k++;
                nums2[j] = -100;
                break;
            }
        }
    }
    *returnSize = k;
    return result;
}

该方法：执行用时：12 ms, 在所有 C 提交中击败了24.56%的用户，内存消耗：5.9 MB, 在所有 C 提交中击败了76.20%的用户。

方法二：

先排序再比较。

int cmp(const void* _a, const void* _b) {
    int *a = _a, *b = (int*)_b;
    return *a == *b ? 0 : *a > *b ? 1 : -1;
}
int* intersect(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize){
    int* result;
    int min;
    if(nums1Size > nums2Size)
        min = nums2Size;
    else
        min = nums1Size;
    result = (int*)malloc(sizeof(int) * min);
    int k = 0;
    
    qsort(nums1, nums1Size, sizeof(int), cmp);
    qsort(nums2, nums2Size, sizeof(int), cmp);
    int i = 0;
    int j = 0;
    while(i<nums1Size && j<nums2Size){
        if(nums1[i] < nums2[j]){
            i ++;
        }
        else if (nums1[i] == nums2[j]){
            result[k] = nums1[i];
            i++;
            j++;
            k++;
        }
        else{
            j++;
        }
    }

    *returnSize = k;
    return result;
}

该方法：执行用时：4 ms, 在所有 C 提交中击败了98.57%的用户，内存消耗：6.2 MB, 在所有 C 提交中击败了26.32%的用户

总结

一个方法内存占的少，一个方法运行的更快。