# 350. Intersection of Two Arrays II

題目：<https://leetcode.com/problems/intersection-of-two-arrays-ii/>

解法一：直接解，先用一個 hash table 來計數紀綠 num1 中數字的出現次數，叫做 countTable ，其中 countTable 的 key 為數字，value 為出現次數，接著找 nums2 的數字是否有在 countTable 出現，如果有的話，記錄到另一個 hash table，叫做 interTable，並減少 countTable 的次數記錄，最後將 interTable 傳換成 array 的形式輸出。

PS: python 使用內建的型態 dict，C 使用 leetcode 額外支援的型態 uthash。

Python3：

class Solution:
    def intersect(self, nums1: list[int], nums2: list[int]) -> list[int]:
        countTable = dict()
        for num in nums1:
            if num in countTable:
                countTable[num] += 1
            else:
                countTable[num] = 1
        interTable = dict()
        for num in nums2:
            if num in countTable:
                if num in interTable:
                    interTable[num] += 1
                else:
                    interTable[num] = 1
                if countTable[num] > 1:
                    countTable[num] -= 1
                else:
                    del countTable[num]
        output = []
        for num, count in interTable.items():
            output += [num] * count
        return output

if __name__ == '__main__':
    nums1 = [1, 2, 2, 1]
    nums2 = [2, 2]

    ans = Solution().intersect(nums1, nums2)
    print(ans)

C：

#include <stdio.h>
#include <stdlib.h>
#include "uthash.h"

typedef struct {
    int key;
    int value;
    UT_hash_handle hh;
} hashEntry;

int* intersect(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) {
    hashEntry *countTable = NULL;
    hashEntry *cur = NULL;
    for (int i = 0; i < nums1Size; i++) {
        HASH_FIND_INT(countTable, &nums1[i], cur);
        if (cur != NULL) {
            cur->value += 1;
        } else {
            cur = (hashEntry*)malloc(sizeof(hashEntry));
            cur->key = nums1[i];
            cur->value = 1;
            HASH_ADD_INT(countTable, key, cur);
        }
    }
    hashEntry *interTable = NULL;
    hashEntry *tmp = NULL;
    for (int i = 0; i < nums2Size; i++) {
        HASH_FIND_INT(countTable, &nums2[i], cur);
        if (cur != NULL) {
            HASH_FIND_INT(interTable, &nums2[i], tmp);
            if (tmp != NULL) {
                tmp->value++;
            } else {
                tmp = (hashEntry*)malloc(sizeof(hashEntry));
                tmp->key = nums2[i];
                tmp->value = 1;
                HASH_ADD_INT(interTable, key, tmp);
            }
            if (cur->value > 1) {
                cur->value--;
            } else {
                HASH_DEL(countTable, cur);
                free(cur);
            }
        }
    }
    int *output = NULL;
    *returnSize = 0;
    int i = 0;
    HASH_ITER(hh, interTable, cur, tmp) {
        *returnSize += cur->value;
        output = (int*)realloc(output, sizeof(int) * (*returnSize));
        while (i < *returnSize)
            output[i++] = cur->key;
        HASH_DEL(interTable, cur);
        free(cur);
    }
    HASH_ITER(hh, countTable, cur, tmp) {
        HASH_DEL(countTable, cur);
        free(cur);
    }
    return output;
}

int main()
{
    int nums1[] = {1, 2, 2, 1};
    int nums1Size = sizeof(nums1) /  sizeof(nums1[0]);
    int nums2[] = {2, 2,};
    int nums2Size = sizeof(nums2) /  sizeof(nums2[0]);
    
    
    int returnSize;
    int* ans = intersect(nums1, nums1Size, nums2, nums2Size, &returnSize);
    for (int i = 0; i < returnSize; i++)
        printf("%d\n", ans[i]);
    return 0;
}

解法二：二元搜尋法，建立一個 output 陣列，將 nums1 排序，接著將 nums2 每個元素依序搜尋是否有在 nums1 中，有的話將此元素加入 output 陣列，並從 nums1 刪除此元素。

Python3：

class Solution:
    def intersect(self, nums1: list[int], nums2: list[int]) -> list[int]:
        def binarySearch(arr, target):
            left = 0
            right = len(arr) - 1
            while left <= right:
                mid = (left + right) // 2
                if arr[mid] > target:
                    right = mid - 1
                elif arr[mid] < target:
                    left = mid + 1
                else:
                    return mid
            return ~left
        nums1.sort()
        output = []
        for num in nums2:
            idx = binarySearch(nums1, num)
            if idx >= 0:
                output.append(num)
                del nums1[idx]
        return output

if __name__ == '__main__':
    nums1 = [1, 2, 2, 1]
    nums2 = [2, 2]

    ans = Solution().intersect(nums1, nums2)
    print(ans)

C：

#include <stdio.h>
#include <stdlib.h>

int binarySearch(int* arr, int arrSize, int target) {
    int left = 0, right = arrSize - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (arr[mid] > target)
            right = mid - 1;
        else if (arr[mid] < target)
            left = mid + 1;
        else
            return mid;
    }
    return ~left;
}

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

int* intersect(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) {
    qsort(nums1, nums1Size, sizeof(int), cmpfunc);
    int * output = (int*)malloc(sizeof(int) * 1000);
    *returnSize = 0;
    for (int i = 0; i < nums2Size; i++) {
        int idx = binarySearch(nums1, nums1Size, nums2[i]);
        if (idx >= 0) {
            output[(*returnSize)++] = nums2[i];
            nums1Size--;
            for (int j = idx; j < nums1Size; j++)
                nums1[j] = nums1[j + 1];
        }
    }
    return output;
}

int main()
{
    int nums1[] = {4, 9, 5};
    int nums1Size = sizeof(nums1) / sizeof(nums1[0]);
    int nums2[] = {9, 4, 9, 8, 4};
    int nums2Size = sizeof(nums2) / sizeof(nums2[0]);
    
    int returnSize;
    int * ans = intersect(nums1, nums1Size, nums2, nums2Size, &returnSize);
    for(int i = 0; i < returnSize; i++)
        printf("%d ", ans[i]);
    printf("\n");
    return 0;
}

###### tags: `leetcode` `hash table` `binary search`