LeetCode 349. 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]

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

Note:
Each element in the result must be unique.
The result can be in any order.

解析

求两个数组的交集，如果用java中的set来实现的话，此题就没有什么难度。但是用C语言的话还是需要注意一下细节上的处理。
最简单的方法是依次判断，如果相等的话就加入到returnArr中，这种方法过于简单，在这里就不做示例。
笔者的思路是先将两个数组排序，然后依次判等，如果不等++i或++j后移，如果相等，则加入到returnArr中，但是要注意去除重复，在returnArr中含有的元素就不要再次添加。

代码（C语言）

int comp(const void* a, const void* b);
int* intersection(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), comp);
    qsort(nums2, nums2Size, sizeof(int), comp);
    
    for (int i = 0, j = 0; i < nums1Size && j < nums2Size;) {
        while (i < nums1Size && nums1[i] < nums2[j])
            ++i;
        
        if (nums1[i] == nums2[j]) {
            returnNums[*returnSize] = nums1[i];
            
            // remove duplicate
            while (i < nums1Size && nums1[i] == returnNums[*returnSize])
                ++i;
            while (j< nums2Size && nums2[j] == returnNums[*returnSize])
                ++j;
            
            ++(*returnSize);
        }
        
        while (j < nums2Size && nums2[j] < nums1[i])
            ++j;
    }
    
    return returnNums;
}

int comp(const void* a, const void* b) {
    return *(int*)a - *(int*)b;
}

上述代码是拿nums1和nums2进行比较，利用了库函数qsort，这样就不用手动编写排序算法，可以节省些时间。