哈希
解题思路
定义两个 hash 数据结构的 Set 集合，一个用于存储 nums1 并和 nums2 对比是否存在交集，存在则 计数 +1；
有交集且存在数量大于 0 放入结果，并 计数 -1；
复杂度
-
时间复杂度：
O(m+n)，其中 m 和 n 分别是两个数组的长度，需要遍历两个数组并对哈希表进行操作； -
空间复杂度：
O(min(m,n))，其中 m 和 n 分别是两个数组的长度，对较短的数组进行哈希表的操作，哈希表的大小不会超过较短的数组的长度；
代码实现
var intersect = function (nums1, nums2) {
if (nums1.length > nums2.length) return intersect(nums2, nums1);
const hash = new Map();
const res = [];
for (let i = 0; i < nums1.length; i++) {
let num = nums1[i];
let count = hash.has(num) ? hash.get(num) : 0;
hash.set(num, ++count);
}
for (let i = 0; i < nums2.length; i++) {
let num = nums2[i];
if (hash.has(num) && hash.get(num) > 0) {
res.push(num);
let count = hash.get(num);
hash.set(num, --count);
}
}
return res;
};
排序 + 双指针
解题思路
如果两个数组是有序的，则可以使用双指针的方法得到两个数组的交集；
首先对两个数组进行排序，然后使用两个指针遍历两个数组；
- 初始时，两个指针分别指向两个数组的头部；
- 每次比较两个指针指向的两个数组中的数字，如果两个数字不相等，则将指向较小数字的指针右移一位；
- 如果两个数字相等，将该数字添加到答案，并将两个指针都右移一位；
- 当至少有一个指针超出数组范围时，遍历结束；
复杂度
-
时间复杂度：
O(mlogm+nlogn)，其中 m 和 n 分别是两个数组的长度； -
空间复杂度：
O(mlogm+nlogn)，其中 m 和 n 分别是两个数组的长度，空间复杂度主要取决于排序使用的额外空间；
代码实现
var intersect = function (nums1, nums2) {
const res = [];
let inx1 = 0;
let inx2 = 0;
nums1.sort((a, b) => a - b);
nums2.sort((a, b) => a - b);
while (inx1 < nums1.length && inx2 < nums2.length) {
if (nums1[inx1] === nums2[inx2]) {
res.push(nums1[inx1]);
inx1++;
inx2++;
} else if (nums1[inx1] > nums2[inx2]) {
inx2++;
} else {
inx1++;
}
}
return res;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 34. 在排序数组中查找元素的第一个和最后一个位置
上一篇
评论
