# 349. Intersection of Two Arrays

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

解法一：直接解，將輸入轉換成 set，取兩個 set 的交集，最後轉換回陣列輸出。

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

Python3：

class Solution:
    def intersection(self, nums1: list[int], nums2: list[int]) -> list[int]:
        return list(set(nums1) & set(nums2))

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

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

C：

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

typedef struct {
    int id;
    UT_hash_handle hh;
} hashEntry;

int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) {
    // set 1
    hashEntry *hashSet1 = NULL;
    hashEntry *cur1, *cur2, *tmp;
    for (int i = 0; i < nums1Size; i++) {
        HASH_FIND_INT(hashSet1, &nums1[i], cur1);
        if (cur1 == NULL) {
            cur1 = (hashEntry*)malloc(sizeof(hashEntry));
            cur1->id = nums1[i];
            HASH_ADD_INT(hashSet1, id, cur1);
        }
    }
    // intersection set
    hashEntry *hashSet2 = NULL;
    for (int i = 0; i < nums2Size; i++) {
        HASH_FIND_INT(hashSet1, &nums2[i], cur1);
        HASH_FIND_INT(hashSet2, &nums2[i], cur2);
        if (cur1 != NULL && cur2 == NULL) {
            cur2 = (hashEntry*)malloc(sizeof(hashEntry));
            cur2->id = nums2[i];
            HASH_ADD_INT(hashSet2, id, cur2);
        }
    }
    // output
    unsigned int count = HASH_COUNT(hashSet2);
    int * output = (int*)malloc(sizeof(int) * count);
    *returnSize = 0;
    HASH_ITER(hh, hashSet2, cur2, tmp) {
        output[(*returnSize)++] = cur2->id;
        HASH_DEL(hashSet2, cur2);
        free(cur2);
    }
    HASH_ITER(hh, hashSet1, cur1, tmp) {
        HASH_DEL(hashSet1, cur1);
        free(cur1);
    }
    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 = intersection(nums1, nums1Size, nums2, nums2Size, &returnSize);
    for(int i = 0; i < returnSize; i++)
        printf("%d\n", ans[i]);

    return 0;
}

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

Python3：

class Solution:
    def intersection(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:
            if binarySearch(nums1, num) >= 0:
                idx = binarySearch(output, num)
                if idx < 0:
                    output.insert(~idx, num)
        return output

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

    ans = Solution().intersection(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* intersection(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++) {
        if (binarySearch(nums1, nums1Size, nums2[i]) >= 0) {
            int idx = binarySearch(output, *returnSize, nums2[i]);
            if (idx < 0) {
                idx = ~idx;
                for (int j = (*returnSize); j > idx; j--)
                    output[j] = output[j - 1];
                output[idx] = nums2[i];
                (*returnSize)++;
            }
        }
    }
    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 = intersection(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`