[LeetCode刷題筆記] 350 - Intersection of Two Arrays II

題目描述：

Given two arrays, write a function to compute their intersection.

Example 1:

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

Example 2:

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

Note:

• Each element in the result should appear as many times as it shows in both arrays.
• The result can be in any order.

Follow up:

• What if the given array is already sorted? How would you optimize your algorithm?
• What if nums1’s size is small compared to nums2’s size? Which algorithm is better?
• What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?

一刷題解（Binary Search）：

這題在使用Binary Search求解時，與上一題「Intersection Of Two Arrays」是一樣的。只是上一題在把共同的元素加到結果數組時要確保元素的唯一性，而這一題就不需要了。

public class Solution
{
    public int[] Intersect(int[] nums1, int[] nums2)
    {
        List<int> nums1Copy = nums1.ToList();
        List<int> nums2Copy = nums2.ToList();
        List<int> resList = new List<int>();
        
        bool isNums1Longer = nums1Copy.Count > nums2Copy.Count;
        if(isNums1Longer)
        {
            nums1Copy.Sort();
        }
        else
        {
            nums2Copy.Sort();
        }
        
        foreach(int i in isNums1Longer ? nums2Copy : nums1Copy)
        {
            if(BS(isNums1Longer ? nums1Copy : nums2Copy, i))
            {
                resList.Add(i);
            }
        }
        
        return resList.ToArray();
    }
    bool BS(int[] nums, int val)
    {
        int left = 0;
        int right = nums.Count - 1;
        int mid = 0;
        
        while(left <= right)
        {
            mid = left + (right - left) / 2;
            if(nums[mid] == val)
            {
                nums.RemoveAt(mid);
                return true;
            }
            else if(nums[mid] > val)
            {
                right = mid - 1;
            }
            else
            {
                left = mid + 1;
            }
        }
        
        return false;
    }
}

二刷題解（Dictionary）：

這一題除了Binary Search以外，也可以用效率更高的Dictionary求解。首先把其中一個數組（arr1）的元素作為鍵，以及這個元素在數組裡的出現次數作為值加到字典裡。然後再遍歷另一個數組（arr2），檢查字典中是否包含裡面的元素，如果是的話，就將字典裡該元素的值（arr1中該元素的出現次數）-1，並將元素加到結果數組中。

public class Solution {
    public int[] Intersect(int[] nums1, int[] nums2) {
        List<int> res = new List<int>();
        //Key : number ; Value : Count
        Dictionary<int, int> numCnt = new Dictionary<int, int>();

        for (int i = 0; i < nums1.Length; i++)
        {
            if (!numCnt.ContainsKey(nums1[i]))
            {
                numCnt.Add(nums1[i], 1);
            }
            else
            {
                numCnt[nums1[i]]++;
            }
        }

        foreach (int i in nums2)
        {
            if (numCnt.ContainsKey(i) && numCnt[i] > 0)
            {
                res.Add(i);
                numCnt[i]--;
            }
        }
        return res.ToArray();
    }
}