C solution with quick sort.


  • 0

    First we need to sort the two arrays. The rest will be very easy.

    /**
     * Return an array of size *returnSize.
     * Note: The returned array must be malloced, assume caller calls free().
     */
    int partition(int*a, int l, int r) {
        int x = a[l];
        while(l < r) {
            while(a[r] > x && l < r) --r;
            if(l < r) {
                a[l] = a[r];
                ++l;
            }
            while(a[l] < x && l < r) ++l;
            if(l < r) {
                a[r] = a[l];
                --r;
            }
        }
        a[l] = x;
        return l;
    }
    
    void quick_sort(int* a, int l, int r) {
        if(l < r) {
            int m = partition(a, l, r);
            quick_sort(a, l, m-1);
            quick_sort(a, m+1, r);
        }
    }
    
    int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) {
        quick_sort(nums1, 0, nums1Size-1);
        quick_sort(nums2, 0, nums2Size-1);
        int* result = (int*)malloc((nums1Size > nums2Size ? nums1Size : nums2Size) * sizeof(int));
        int i = 0, j = 0;
        *returnSize = 0;
        while(i < nums1Size && j < nums2Size) {
            if(nums1[i] == nums2[j]) {
                if(*returnSize > 0 && result[(*returnSize)-1] != nums1[i])
                    result[(*returnSize)++] = nums1[i];
                else if(0 == *returnSize)
                    result[(*returnSize)++] = nums1[i];
                ++i;
                ++j;
            }
            else if(nums1[i] > nums2[j]) ++j;
            else ++i;
        }
        return result;
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.