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 intersection(vector & nums1, vector & nums2) { 9 sort(nums1.begin(), nums1.end());10 sort(nums2.begin(), nums2.end());11 12 vector intersect;13 vector ::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::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 hash = new HashSet<>();13 for (int i = 0; i < nums1.length; i++) {14 hash.add(nums1[i]);15 }16 17 HashSet 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 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 set1 = new HashSet<>(); 5 ArrayList 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的代码