算法-两个数组的交集
题目
我的思路
将数组nums1 转成map,然后数组2遍历,依次判断内部元素是否在nums1中,并且结果中不存在当前所遍历的nums2对象。代码如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number[]}
*/
var intersection = function(nums1, nums2) {
let result = [];
let originMap = {};
for (let i = 0; i < nums1.length; i++) {
if (originMap[nums1[i]]) {
originMap[nums1[i]] += 1;
} else {
originMap[nums1[i]] = 1;
}
}
for (let j = 0; j < nums2.length; j++) {
if (originMap[nums2[j]] && (!result.includes(nums2[j]))) {
result.push(nums2[j]);
}
}
return result;
}结果
以上执行用时还是很慢,想着如何优化
- 看题解,发现有个思路比较有趣, 貌似是3s
思路
1) 把第一个数组排序
2) 遍历第二个数组的值,判断是否在第一个数组中,这里使用的是二分法查找的数量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
35
36
37public int[] intersection(int [] nums1, int [] nums2) {
Array.sort(nums1);
Set(Integer) resSet = new HashSet<>();
for(int i = 0; i < nums2.length; i++) {
if (binarySearch(nums1, nums2[i]);
resSet.add(nums2[i])
}
int [] res = new int[resSet.size()];
int k = 0;
for (Integer num: resSet) {
res[k++] = num;
}
return res;
}
private boolean binarySearch(int [] nums, int target) {
int left = 0;
int right = nums.length - 1;
while(left <= right) {
int mid = left + (right - left) / 2;
int midValue = nums[mid];
if (midValue === target) {
return true;
} else if (midValue > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return false;
}