LeetCode:350.Intersection of Two Arrays II 两个数组的交集 II(C语言)

Myth丶恋晨 2023-07-18 09:29 81阅读 0赞

**题目描述：**  
给定两个数组，编写一个函数来计算它们的交集。

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

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/intersection-of-two-arrays-ii  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。  
**解答：**

/** * Note: The returned array must be malloced, assume caller calls free(). */
    int comp(const void *a, const void *b)
    { 
       // return(*(int*)a - *(int*)b);
        int *p1 = (int*)a, *p2 = (int*)b;
        return *p1 > *p2; // 测试用例中有-2147483648，用减号的话会溢出
    }
    
    int* intersect(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize)
    { 
        qsort(nums1, nums1Size, sizeof(int), comp);
        qsort(nums2, nums2Size, sizeof(int), comp);
        
        int *nums=(int *)malloc(sizeof(int)*nums1Size);
        
        int index = 0;
        int i = 0, j = 0, k = 0;
        while(i < nums1Size && j < nums2Size)
        { 
            if(nums1[i] > nums2[j])
            { 
                j++;
            }
            else if(nums1[i] < nums2[j])
            { 
                i++;
            }
            else 
            { 
                nums[k++] = nums1[i];
                j++;
                i++;
            }
        }
        
        *returnSize = k;
        
        return nums;
    }

**运行结果：**  
![在这里插入图片描述][20200325160851308.png]

[20200325160851308.png]: /images/20230528/102ecfaaf5604604ac920c4a4eb17351.png