349. Intersection of Two Arrays

  • 46.2%

https://leetcode.com/problems/intersection-of-two-arrays/?tab=Description

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

1
2
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.

方法一:

先排序,然后双指针遍历

12ms, 42.46%, June.5th, 2016

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
std::sort(nums1.begin(), nums1.end());
std::sort(nums2.begin(), nums2.end());
vector<int> ans;
int i=0, j=0;
while(i<nums1.size() && j<nums2.size()){
if(nums1[i] < nums2[j])
i++;
else if(nums1[i] > nums2[j])
j++;
else {
if(!ans.size() ||ans.back() != nums1[i])
ans.push_back(nums1[i]);
i++;
j++;
}
}
return ans;
}
};

方法二:

一个list转为set,另一个遍历去set里找,找到加入res,

并且从set中删除。

1
2
3
4
5
6
7
8
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
set<int> s(nums1.begin(), nums1.end());
vector<int> out;
for (int x : nums2)
if (s.erase(x))
out.push_back(x);
return out;
}

方法三:

一个建立hash表,遍历另一个,在表里,就加入res,从表里删除。


cpp


https://discuss.leetcode.com/topic/45846/small-c-solution

1
2
3
4
5
6
7
8
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
set<int> s(nums1.begin(), nums1.end());
vector<int> out;
for (int x : nums2)
if (s.erase(x))
out.push_back(x);
return out;
}

https://leetcode.com/discuss/103224/my-c-solution-with-sort

12ms, 42.46%, June.5th, 2016

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
std::sort(nums1.begin(), nums1.end());
std::sort(nums2.begin(), nums2.end());
vector<int> ans;
int i=0, j=0;
while(i<nums1.size() && j<nums2.size()){
if(nums1[i] < nums2[j])
i++;
else if(nums1[i] > nums2[j])
j++;
else {
if(!ans.size() ||ans.back() != nums1[i])
ans.push_back(nums1[i]);
i++;
j++;
}
}
return ans;
}
};

https://leetcode.com/discuss/103365/8ms-concise-c-using-unordered_set

16ms, 17.41%, June.5th, 2016

8ms concise C++ using unordered_set

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> m(nums1.begin(), nums1.end());
vector<int> ans;
for(auto a:nums2){
if(m.count(a)){
ans.push_back(a);
m.erase(a);
}
}
return ans;
}
};

python

Solution Mine:

52ms, 60 / 60, 76.78%, June.5th, 2016

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
def intersection(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: List[int]
"""
nums1 = set(nums1)
nums2 = set(nums2)
rtype = [i for i in nums1 if i in nums2]
return rtype

Solution 1:

https://leetcode.com/discuss/103709/python-code-3-lines-using-set

June.5th, 2016

1
2
3
4
5
6
7
8
9
10
class Solution(object):
def intersection(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: List[int]
"""
nums1=set(nums1)
nums2=set(nums2)
return list(nums1&nums2)

Solution 2:

https://leetcode.com/discuss/103709/python-code-3-lines-using-set

1
2
3
4
5
6
7
8
class Solution(object):
def intersection(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: List[int]
"""
return list(set(nums1) & set(nums2))

https://discuss.leetcode.com/topic/45727/four-python-solutions-with-simple-explanation

Solution 1:

use set operation in python, one-line solution.

1
2
3
4
5
6
7
8
class Solution(object):
def intersection(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: List[int]
"""
return list(set(nums1) & set(nums2))

Solution 2:

brute-force searching, search each element of the first list in the second list. (to be more efficient, you can sort the second list and use binary search to accelerate)

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
def intersection(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: List[int]
"""
res = []
for i in nums1:
if i not in res and i in nums2:
res.append(i)
return res

Solution 3:

use dict/hashmap to record all nums appeared in the first list, and then check if there are nums in the second list have appeared in the map.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
def intersection(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: List[int]
"""
res = []
map = {}
for i in nums1:
map[i] = map[i]+1 if i in map else 1
for j in nums2:
if j in map and map[j] > 0:
res.append(j)
map[j] = 0

return res

Solution 4:

sort the two list, and use two pointer to search in the lists to find common elements.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution(object):
def intersection(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: List[int]
"""
res = []
nums1.sort()
nums2.sort()
i = j = 0
while (i < len(nums1) and j < len(nums2)):
if nums1[i] > nums2[j]:
j += 1
elif nums1[i] < nums2[j]:
i += 1
else:
if not (len(res) and nums1[i] == res[len(res)-1]):
res.append(nums1[i])
i += 1
j += 1

return res

java

https://discuss.leetcode.com/topic/45685/three-java-solutions

7ms, 34.67%, June.5th, 2016

Use two hash sets

Time complexity: O(n)

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

https://discuss.leetcode.com/topic/45685/three-java-solutions

Sort both arrays, use two pointers

Time complexity: O(nlogn)

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

https://discuss.leetcode.com/topic/45685/three-java-solutions

Binary search

Time complexity: O(nlogn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
Set<Integer> set = new HashSet<>();
Arrays.sort(nums2);
for (Integer num : nums1) {
if (binarySearch(nums2, num)) {
set.add(num);
}
}
int i = 0;
int[] result = new int[set.size()];
for (Integer num : set) {
result[i++] = num;
}
return result;
}

public boolean binarySearch(int[] nums, int target) {
int low = 0;
int high = nums.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (nums[mid] == target) {
return true;
}
if (nums[mid] > target) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return false;
}
}

https://discuss.leetcode.com/topic/45879/5ms-java-using-1-hashset-and-time-complexity-of-o-m-n

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
HashSet<Integer> set = new HashSet<Integer>();
ArrayList<Integer> res = new ArrayList<Integer>();
//Add all elements to set from array 1
for(int i =0; i< nums1.length; i++) set.add(nums1[i]);
for(int j = 0; j < nums2.length; j++) {
// If present in array 2 then add to res and remove from set
if(set.contains(nums2[j])) {
res.add(nums2[j]);
set.remove(nums2[j]);
}
}
// Convert ArrayList to array
int[] arr = new int[res.size()];
for (int i= 0; i < res.size(); i++) arr[i] = res.get(i);
return arr;
}
}

谢谢你,可爱的朋友。