代码拉取完成,页面将自动刷新
给定两个数组,编写一个函数来计算它们的交集。
输入:nums1 = [1,2,2,1], nums2 = [2,2]
输出:[2]
输入:nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出:[9,4]
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number[]}
*/
var intersection = function(nums1, nums2) {
nums1.sort((a, b) => a - b);
nums2.sort((a, b) => a - b);
let target = [];
let i = 0, k = 0;
let n1 = nums1.length, n2 = nums2.length;
while(i<n1 && k<n2){
if(nums1[i] < nums2[k]){
++i;
}else if(nums1[i] > nums2[k]){
++k;
}else{
let last = target.length-1;
if(target[last] !== nums1[i]) target.push(nums1[i]);
++i;
++k;
}
}
return target;
};
比较常规的题目,计算两个数组的交集最简单的方式就是遍历数组nums1
,对于其中的每个元素,遍历数组nums2
判断该元素是否在数组nums2
中,如果存在,则将该元素添加到返回值,这样的方式时间复杂度是O(mn)
,在这里使用排序加双指针的方式,首先对于两个数组分别进行排序,之后分别对于两个数组设立指针进行遍历,对比两个指针所指向的元素,较小的值的指针后移,如果相等则判断是否已经在目标数组中,不在则将其推入数组,之后同时将两个指针后移,最终返回目标数组即可。首先将两个数组分别从小到大进行排序,之后定义目标数组target
,以及两个指针i
、k
与两个数组的长度n1
、n2
,定义循环,在两个指针分别小于其指向的目标数组的长度下执行循环,如果i
指针指向的值小于k
指针指向的值,将i
指针后移,如果大于则将k
指针后移,如果相等则首先得到目标数组的最后一个值的索引,当然在数组为空的情况下会得到-1
,在Js
中会取得undefined
值,在下方比较时不会相等,之后比较最后一个值是否与此时指针指向的值相等,不相等则将值推入数组,这样用来进行去重操作,之后将两个指针分别后移,循环结束后返回目标数组即可。
https://github.com/WindrunnerMax/EveryDay
https://leetcode-cn.com/problems/intersection-of-two-arrays/
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。