LeetCode 349. Intersection of Two Arrays

原题链接在这里：https://leetcode.com/problems/intersection-of-two-arrays/

题目：

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

Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2].

Note:

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

题解：

用一个HashSet 来保存nums1的每个element.

再iterate nums2, 若HashSet contains nums2[i], 把nums2[i]加到res中，并把nums[i]从HashSet中remove掉.

Time Complexity: O(nums1.length + nums2.length). Space: O(nums1.length).

AC Java:

 1 public class Solution {
 2     public int[] intersection(int[] nums1, int[] nums2) {
 3         HashSet<Integer> nums1Hs = new HashSet<Integer>();
 4         for(int num : nums1){
 5             nums1Hs.add(num);
 6         }
 7         
 8         List<Integer> res = new ArrayList<Integer>();
 9         for(int num : nums2){
10             if(nums1Hs.contains(num)){
11                 res.add(num);
12                 nums1Hs.remove(num);
13             }
14         }
15         int [] resArr = new int[res.size()];
16         int i = 0;
17         for(int num : res){
18             resArr[i++] = num;
19         }
20         return resArr;
21     }
22 }

也可以使用两个HashSet.

Time Complexity: O(nums1.length + nums2.length). Space: O(nums1.length).

AC Java:

 1 public class Solution {
 2     public int[] intersection(int[] nums1, int[] nums2) {
 3         HashSet<Integer> nums1Hs = new HashSet<Integer>();
 4         HashSet<Integer> intersectHs = new HashSet<Integer>();
 5         for(int num : nums1){
 6             nums1Hs.add(num);
 7         }
 8         for(int num : nums2){
 9             if(nums1Hs.contains(num)){
10                 intersectHs.add(num);
11             }
12         }
13         
14         int [] res = new int[intersectHs.size()];
15         int i = 0;
16         for(int num : intersectHs){
17             res[i++] = num;
18         }
19         return res;
20     }
21 }

Sort nums1 and nums2, 再用双指针从头iterate两个sorted array.

Time Complexity: O(nlogn). Space: O(1).

AC Java:

 1 public class Solution {
 2     public int[] intersection(int[] nums1, int[] nums2) {
 3         Arrays.sort(nums1);
 4         Arrays.sort(nums2);
 5         HashSet<Integer> hs = new HashSet<Integer>();
 6         int i = 0;
 7         int j = 0;
 8         while(i<nums1.length && j<nums2.length){
 9             if(nums1[i] < nums2[j]){
10                 i++;
11             }else if(nums1[i] > nums2[j]){
12                 j++;
13             }else{
14                 hs.add(nums1[i]);
15                 i++;
16                 j++;
17             }
18         }
19         
20         int [] resArr = new int[hs.size()];
21         int k = 0;
22         for(int num : hs){
23             resArr[k++] = num; 
24         }
25         return resArr;
26     }
27 }

sort nums1, 然后nums2 array 每一个element在 sorted 上做binary search.

Time Complexity: O(mlogm + nlogm), m = nums1.length, n = nums2.length.

Space: O(resArr.length).

AC Java:

 1 public class Solution {
 2     public int[] intersection(int[] nums1, int[] nums2) {
 3         HashSet<Integer> res = new HashSet<Integer>();
 4         Arrays.sort(nums1);
 5         for(int num : nums2){
 6             if(binarySearch(nums1, num)){
 7                 res.add(num);
 8             }
 9         }
10         
11         int [] resArr = new int[res.size()];
12         int i = 0;
13         for(int num : res){
14             resArr[i++] = num;
15         }
16         return resArr;
17     }
18     
19     private boolean binarySearch(int [] nums, int target){
20         int low = 0;
21         int high = nums.length-1;
22         while(low <= high){
23             int mid = low + (high-low)/2;
24             if(nums[mid] < target){
25                 low = mid+1;
26             }else if(nums[mid] > target){
27                 high = mid-1;
28             }else{
29                 return true;
30             }
31         }
32         return false;
33     }
34 }

跟上Intersection of Two Arrays II, Intersection of Three Sorted Arrays.