350. Intersection of Two Arrays II

  • 44.0%

https://leetcode.com/problems/intersection-of-two-arrays-ii/

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

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

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?

先排序 后两个指针遍历 算法复杂度n*logn,因为有排序。

使用hash表,复杂度为n,所以使用hash表,效果更好。


java

Solution 1:

https://leetcode.com/discuss/103835/ac-solution-using-java-hashmap

7ms, 63.08%, 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
23
24
25
26
27
28
public class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
ArrayList<Integer> result = new ArrayList<Integer>();
for(int i = 0; i < nums1.length; i++)
{
if(map.containsKey(nums1[i])) map.put(nums1[i], map.get(nums1[i])+1);
else map.put(nums1[i], 1);
}

for(int i = 0; i < nums2.length; i++)
{
if(map.containsKey(nums2[i]) && map.get(nums2[i]) > 0)
{
result.add(nums2[i]);
map.put(nums2[i], map.get(nums2[i])-1);
}
}

int[] r = new int[result.size()];
for(int i = 0; i < result.size(); i++)
{
r[i] = result.get(i);
}

return r;
}
}

cpp

Solution Mine:

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
vector<int> intersect(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{
ans.push_back(nums1[i]);
i++;
j++;
}
}
return ans;
}
};

Solution 2:

https://leetcode.com/discuss/103787/table-solution-pointers-solution-with-time-space-complexity

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

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
unordered_map<int,int> dict;
vector<int> res;
for(int i=0; i<nums1.size();i++) dict[nums1[i]]++;
for(int j=0; j<nums2.size();j++)
if(--dict[nums2[j]] >= 0) res.push_back(nums2[j]);
return res;
}
};

python

Solution 1:

https://leetcode.com/discuss/104046/python-o-n-simple-solution

60ms, 61.07%, June.5th, 2016

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
def intersect(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: List[int]
"""
result = []
n_dict = dict()
for n in nums1:
n_dict[n] = n_dict.get(n, 0) + 1
for n2 in nums2:
if n_dict.get(n2, 0) > 0:
result.append(n2)
n_dict[n2] = n_dict[n2] - 1
return result

Solution 2:

https://leetcode.com/discuss/103895/straightforward-python-solution-based-on-sort

62ms, 88.22%, 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(object):
def intersect(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: List[int]
"""
nums1.sort()
nums2.sort()
i=0
j=0
res = []
while i<len(nums1) and j<len(nums2):
if nums1[i] == nums2[j]:
res.append(nums1[i])
i += 1
j += 1
elif nums1[i] < nums2[j]:
i += 1
else:
j += 1
return res
谢谢你,可爱的朋友。