LeetCode 350. Intersection of Tw

题目

Given two arrays, write a function to compute their intersection.

Example 1:
Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2,2]

Example 2:
Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [4,9]

Note:
Each element in the result should appear as many times as it shows in both arrays.
The result can be in any order.

解析

本题和349题基本一致，不同的区别在于349题所得到的集合中需要去重，本题则需要把所有重复的都添加到其中。
因此，在循环的过程中需要把去重的while循环去掉，只作判断即可。

代码（C语言）

int compareInt(const void* a, const void* b);
int* intersect(int* nums1, int nums1Size, int* nums2, int nums2Size,
               int* returnSize) {
    int shortSize = nums1Size > nums2Size ? nums2Size : nums1Size;
    int* returnNums = (int*)calloc(shortSize, sizeof(int));
    
    (*returnSize) = 0;
    
    // sort using qsort
    qsort(nums1, nums1Size, sizeof(int), compareInt);
    qsort(nums2, nums2Size, sizeof(int), compareInt);
    
    int i = 0, j = 0;
    while (i < nums1Size && j < nums2Size) {
        if (nums1[i] == nums2[j]) {
            returnNums[(*returnSize)] = nums1[i];
            
            ++i;
            ++j;
            ++(*returnSize);
        } else if (nums1[i] < nums2[j])
            ++i;
        else
            ++j;
    }
    
    return returnNums;
}

int compareInt(const void* a, const void* b) {
    if ((*(int*)a) == (*(int*)b))
        return 0;
    
    return (*(int*)a) > (*(int*)b) ? 1: -1;
}