题目来源：https://leetcode.com/problems/intersection-of-two-arrays-ii
题目难度：Easy
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 {
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;
}
}
|
复杂度分析
HashMap 的 get() 时间复杂度为 $O(1)$。
解答2[Java]：
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
|
class {
public int[] intersect(int[] nums1, int[] nums2) {
List<Integer> intersection = new ArrayList<>();
Arrays.sort(nums1);
Arrays.sort(nums2);
int i = 0;
int j = 0;
while (i < nums1.length && j < nums2.length) {
if (nums1[i] == nums2[j]) {
intersection.add(nums2[j]);
i++;
j++;
} else if (nums1[i] > nums2[j]) {
j++;
} else {
i++;
}
}
int[] res = new int[intersection.size()];
for (int k = 0; k < intersection.size(); k++) {
res[k] = intersection.get(k);
}
return res;
}
}
|
思路
先对数组进行排序，然后两个数组分别设一个指针，分别比较。
近期评论