547. Intersection of Two Arrays【easy】

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

Notice

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

Example

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

Challenge

Can you implement it in three different algorithms?

解法一：

 1 class Solution {
 2 public:
 3     /**
 4      * @param nums1 an integer array
 5      * @param nums2 an integer array
 6      * @return an integer array
 7      */
 8     vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
 9         sort(nums1.begin(), nums1.end());
10         sort(nums2.begin(), nums2.end());
11 
12         vector<int> intersect;
13         vector<int>::iterator it1 = nums1.begin(), it2 = nums2.begin();
14         while ((it1 != nums1.end()) && (it2 != nums2.end())) {
15             if (*it1 < *it2) {
16                 it1++;
17             } else if (*it1 > *it2) {
18                 it2++;
19             } else {
20                 intersect.push_back(*it1); 
21                 it1++; it2++;
22             }
23         }
24         
25         auto last = unique(intersect.begin(), intersect.end());
26         intersect.erase(last, intersect.end());
27         return intersect;
28     }
29 };

sort & merge

类属性算法unique的作用是从输入序列中“删除”所有相邻的重复元素。该算法删除相邻的重复元素，然后重新排列输入范围内的元素，并且返回一个迭代器（容器的长度没变，只是元素顺序改变了），表示无重复的值范围得结束。在STL中unique函数是一个去重函数， unique的功能是去除相邻的重复元素(只保留一个),其实它并不真正把重复的元素删除，是把重复的元素移到后面去了，然后依然保存到了原数组中，然后返回去重后最后一个元素的地址，因为unique去除的是相邻的重复元素，所以一般用之前都会要排一下序。

常见的用法如下：

 1 /*
 2  * sort words alphabetically so we can find the duplicates 
 3  */ 
 4 sort(words.begin(), words.end()); 
 5 
 6 /* eliminate duplicate words: 
 7  * unique reorders words so that each word appears once in the 
 8  * front portion of words and returns an iterator one past the unique range; 
 9  * erase uses a vector operation to remove the nonunique elements 
10  */ 
11  vector<string>::iterator end_unique =  unique(words.begin(), words.end()); 
12  
13  words.erase(end_unique, words.end());

参考@NineChapter的代码

解法二：

 1 public class Solution {
 2     /**
 3      * @param nums1 an integer array
 4      * @param nums2 an integer array
 5      * @return an integer array
 6      */
 7     public int[] intersection(int[] nums1, int[] nums2) {
 8         Arrays.sort(nums1);
 9         Arrays.sort(nums2);
10         
11         int i = 0, j = 0;
12         int[] temp = new int[nums1.length];
13         int index = 0;
14         while (i < nums1.length && j < nums2.length) {
15             if (nums1[i] == nums2[j]) {
16                 if (index == 0 || temp[index - 1] != nums1[i]) {
17                     temp[index++] = nums1[i];
18                 }
19                 i++;
20                 j++;
21             } else if (nums1[i] < nums2[j]) {
22                 i++;
23             } else {
24                 j++;
25             }
26         }
27         
28         int[] result = new int[index];
29         for (int k = 0; k < index; k++) {
30             result[k] = temp[k];
31         }
32         
33         return result;
34     }
35 }

sort & merge

参考@NineChapter的代码

解法三：

 1 public class Solution {
 2     /**
 3      * @param nums1 an integer array
 4      * @param nums2 an integer array
 5      * @return an integer array
 6      */
 7     public int[] intersection(int[] nums1, int[] nums2) {
 8         if (nums1 == null || nums2 == null) {
 9             return null;
10         }
11         
12         HashSet<Integer> hash = new HashSet<>();
13         for (int i = 0; i < nums1.length; i++) {
14             hash.add(nums1[i]);
15         }
16         
17         HashSet<Integer> resultHash = new HashSet<>();
18         for (int i = 0; i < nums2.length; i++) {
19             if (hash.contains(nums2[i]) && !resultHash.contains(nums2[i])) {
20                 resultHash.add(nums2[i]);
21             }
22         }
23         
24         int size = resultHash.size();
25         int[] result = new int[size];
26         int index = 0;
27         for (Integer num : resultHash) {
28             result[index++] = num;
29         }
30         
31         return result;
32     }
33 }

hash map

参考@NineChapter的代码

解法四：

 1 public class Solution {
 2     /**
 3      * @param nums1 an integer array
 4      * @param nums2 an integer array
 5      * @return an integer array
 6      */
 7     public int[] intersection(int[] nums1, int[] nums2) {
 8         if (nums1 == null || nums2 == null) {
 9             return null;
10         }
11         
12         HashSet<Integer> set = new HashSet<>();
13         
14         Arrays.sort(nums1);
15         for (int i = 0; i < nums2.length; i++) {
16             if (set.contains(nums2[i])) {
17                 continue;
18             }
19             if (binarySearch(nums1, nums2[i])) {
20                 set.add(nums2[i]);
21             }
22         }
23         
24         int[] result = new int[set.size()];
25         int index = 0;
26         for (Integer num : set) {
27             result[index++] = num;
28         }
29         
30         return result;
31     }
32     
33     private boolean binarySearch(int[] nums, int target) {
34         if (nums == null || nums.length == 0) {
35             return false;
36         }
37         
38         int start = 0, end = nums.length - 1;
39         while (start + 1 < end) {
40             int mid = (end - start) / 2 + start;
41             if (nums[mid] == target) {
42                 return true;
43             }
44             if (nums[mid] < target) {
45                 start = mid;
46             } else {
47                 end = mid;
48             }
49         }
50         
51         if (nums[start] == target) {
52             return true;
53         }
54         if (nums[end] == target) {
55             return true;
56         }
57         
58         return false;
59     }
60 }

sort & binary search

参考@NineChapter的代码

解法五：

 1 public class Solution {
 2     public int[] intersection(int[] nums1, int[] nums2) {
 3         // Write your code here
 4         HashSet<Integer> set1 = new HashSet<>();
 5         ArrayList<Integer> result = new ArrayList<>();
 6         for(int n1 : nums1){
 7             set1.add(n1);
 8         }
 9         for(int n2 : nums2){
10             if(set1.contains(n2)){
11                 result.add(n2);
12                 set1.remove(n2);
13             }
14         }
15         int[] ret = new int[result.size()];
16         for(int i = 0; i < result.size(); i++){
17             ret[i] = result.get(i);
18         }
19         return ret;
20     }
21 };

参考@NineChapter的代码