[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();
  }
}