Problem¶

Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must appear as many times as it shows in both arrays and you may return the result in any order.

Constraints:

• 1 <= nums1.length, nums2.length <= 1000
• 0 <= nums1[i], nums2[i] <= 1000

Example 1:

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

Solve¶

I do exactly this:

• Count all number of both array
• Find intersect number value (don’t care about duplicate)
• Rebuild result array using needed information: <Total time appear both nums> * [value]

class Solution(object):
    def intersect(self, nums1, nums2):
        interset = set(nums1).intersection(set(nums2))
        count = {}
        for i in nums1:
            if i not in count:
                count[i] = [0, 0]
            count[i][0] += 1

        for i in nums2:
            if i not in count:
                count[i] = [0, 0]
            count[i][1] += 1

        result = []
        for key in interset:
            result += min(count[key])* [key]
        return result

Counting, using a large predefined array¶

I need more time to done the same with C, as C not have good hash map for set() available from the language standard library at all, we using fully the provided Constant:

• Count all the number appear on nums1 and nums2, storing in a predefined array that cover all possible number. Which is [0..1000](as 0 <= nums1[i], nums2[i] <= 1000)
• Build up the intersection by going through all possible number, by using the same logic:
  • If our current number i appear on both, adding that i to the intersectArr for the total occur = min(count1[i], count2[i]) times
  • If it not appear occur = 0, go to the next number

Now to the “slow” part, why it slow? Because I need to check:

• The return type is int*, which is a persistence memory in heap, while our intersectArr is allocating inside a C local function scope, which being clear/disappear after going back to main function. So, we need to malloc new memory and transfer intersectArr over one by one.
• The int* returnSize, this is where we have to return the length or our result. It quite confusion as returnSize is a pointer (which why using printf("%d", returnSize) output some thing like 91267892). We need to know syntax to correctly pass the required value to returnSize, which is *returnSize = intersectArrLen.

/**

 * Note: The returned array must be malloced, assume caller calls free().
 */
int* intersect(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize){
    int* result;

    int count1[1005] = {0};
    int count2[1005] = {0};
    int intersectArr[1005] = {0};
    int intersectArrLen = 0;
    int occur = 0;
    for (int i = 0; i < nums1Size; i++) count1[nums1[i]] ++;
    for (int i = 0; i < nums2Size; i++) count2[nums2[i]] ++;

    for (int i = 0; i < 1001; i++){
        occur = count1[i];
        if (count1[i] > count2[i]) occur = count2[i];
        for (int _j = 0; _j < occur; _j ++) {
            intersectArr[intersectArrLen] = i;
            intersectArrLen ++;
        }
    }

    result = (int*)malloc(intersectArrLen * sizeof(int));
    for (int i = 0; i < intersectArrLen; i++){
        result[i] = intersectArr[i];
    }

    *returnSize = intersectArrLen;
    return result;
}