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

題目描述：

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

Example 1:

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

Example 2:

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

Note:

Each element in the result must be unique.
The result can be in any order.

一刷題解（Binary Search）：

這一題要求我們在兩個已知的數組之中，將它們的并集找出來，並將其返回。那麼最直接的方法就是將其中一個數組的元素依次作為在另一個數組中進行查找的目標，如果成功找到，那就代表當前元素是兩個數組的共有的元素之一，然後將它加到我們的結果數組中（加入前，考慮到題目限制 Each element in the result must be unique，因此需要先檢查一下數組裡面是否已經有了這個元素）。

但是如果直接線性查找的話，如果目標元素在另一個數組的尾部時，會導致查找的效率較低(O(n))，因此，為了提高查找效率，我進行了二分查找。但是具體要對哪個數組進行二分查找和芍哪個數組進行遍歷呢？由於長度較長的數組有可能包含了數組較短的數組中的所有元素，因此，二分查找的對象自然是較長的數組，而遍歷的對象就自然是較短的數組。

public class Solution
{
    public int[] Intersection(int[] nums1, int[] nums2)
    {
        //對長度較長的數組排序，準備進行二分查找
        List<int> resList = new List<int>();
        bool isNums1Longer = nums1.Length > nums2.Length;
        if(isNums1Longer)
        {
            Array.Sort(nums1);
        }
        else
        {
            Array.Sort(nums2);
        }
        
        //遍歷較短的數組
        foreach(int num in isNums1Longer ? nums2 : nums1)
        {
            //檢查當前元素是否已存在於結果數組
            if(!resList.Contains(num))
            {
                //把當前元素作為二分查找的目標
                if(BinarySearchValue(isNums1Longer ? nums1 : nums2, num))
                {
                    //找到了就代表是并集元素
                    resList.Add(num);
                }
            }
        }
        return resList.ToArray();
    }
    //標準的二分查找函數
    bool BinarySearchValue(int[] nums, int val)
    {
        int left = 0;
        int right = nums.Length - 1;
        int mid = 0;
        while(left <= right)
        {
            mid = left + (right - left) / 2;
            if(val == nums[mid])
            {
                return true;
            }
            else if(val > nums[mid])
            {
                left = mid + 1;
            }
            else
            {
                right = mid - 1;
            }
        }
        return false;
    }
}

二刷題解（HashSet）：

我是在做LeetCode上的HashTable教學卡時遇到這一題的，然後發現自己曾經用Binary Search做過這一題，決定這次就用HashSet來二刷一下。HashSet有一個好處，就是它可以確保裡面的元素都是唯一的，這使得我們可以事先完成題目中Each element in the result must be unique的限制。因此，在這題裡，我首先分別將兩個數組的元素組成兩個HashSet。然後我再選擇長度較短的一個HashSet，對它進行遍歷，然後仿傚教學卡裡的做法，直接使用長度較長的HashtSet中的Contains方法檢查元素是否存在。存在即為并集元素，加到我們的結果列表中，最後將列表返回即可。

public class Solution {
    public int[] Intersection(int[] nums1, int[] nums2) {
        //建構2個HashSet，為兩個數組去重
        HashSet<int> num1Hash = new HashSet<int>(nums1.Length);
        for (int i = 0; i < nums1.Length; i++)
        {
            num1Hash.Add(nums1[i]);
        }

        HashSet<int> num2Hash = new HashSet<int>(nums2.Length);
        for (int i = 0; i < nums2.Length; i++)
        {
            num2Hash.Add(nums2[i]);
        }

        //遍歷較短的HashSet
        bool isNum1HashLonger = num1Hash.Count() > num2Hash.Count();
        List<int> res = new List<int>();
        foreach (int i in (isNum1HashLonger ? num2Hash : num1Hash))
        {
            //使用HashSet.Contains(var element)檢查元素是否存在於長度較長的HashSet中
            if (isNum1HashLonger)
            {
                if (num1Hash.Contains(i))
                {
                    res.Add(i);                      
                }
            }
            else
            {
                if (num2Hash.Contains(i))
                {
                    res.Add(i);
                }
            }
        }

        return res.ToArray();      
    }
}

題目描述：

一刷****題解（Binary Search）：

二刷****題解（HashSet）：

一刷題解（Binary Search）：

二刷題解（HashSet）：