349 Intersection of Two Arrays

1. Question

Given two arrays, write a function to compute their intersection.
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.

2. Implementation

(1) Two Pointers
1
class Solution {
2
public int[] intersection(int[] nums1, int[] nums2) {
3
Set<Integer> set = new HashSet<>();
4
5
Arrays.sort(nums1);
6
Arrays.sort(nums2);
7
8
int i = 0, j = 0;
9
10
while (i < nums1.length && j < nums2.length) {
11
if (nums1[i] < nums2[j]) {
12
++i;
13
}
14
else if (nums1[i] > nums2[j]) {
15
++j;
16
}
17
else {
18
set.add(nums1[i]);
19
++i;
20
++j;
21
}
22
}
23
24
int[] res = new int[set.size()];
25
int index = 0;
26
27
for (int e : set) {
28
res[index++] = e;
29
}
30
return res;
31
}
32
}
Copied!
(2) Binary Search
1
class Solution {
2
public int[] intersection(int[] nums1, int[] nums2) {
3
if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) {
4
return new int[0];
5
}
6
7
Set<Integer> set = new HashSet<>();
8
9
Arrays.sort(nums2);
10
11
for (int i = 0; i < nums1.length; i++) {
12
int index = binarySearch(nums2, nums1[i]);
13
14
if (index != -1) {
15
set.add(nums1[i]);
16
}
17
}
18
19
int[] res = new int[set.size()];
20
int index = 0;
21
22
for (int e : set) {
23
res[index++] = e;
24
}
25
return res;
26
}
27
28
public int binarySearch(int[] nums, int target) {
29
int start = 0, end = nums.length - 1, mid = 0;
30
31
while (start <= end) {
32
mid = start + (end - start) / 2;
33
34
if (nums[mid] == target) {
35
return mid;
36
}
37
else if (nums[mid] < target) {
38
start = mid + 1;
39
}
40
else {
41
end = mid - 1;
42
}
43
}
44
return -1;
45
}
46
}
Copied!

3. Time & Space Complexity

Two Pointers: 时间复杂度O(nlogn + mlogm),n为nums1的长度,m为nums2的长度,空间复杂度O(Math.min(m,n))
Binary Search: 时间复杂度O(nlogn + mlogn), 空间复杂度O(Math.min(m, n))