H5W3
当前位置:H5W3 > 问答 > 正文

js面试题:取出数组中出现两次的值

输入一个长度为n的数组a,其中有的数据出现一次有的出现两次,返回其中出现两次的数据

不开辟额外空间,时间复杂度O(n)

如输入[1, 1, 2, 3, 5, 3]返回 [1, 3]

回答

我估计最符合的就是这个了,但是indexOf也要参与计算复杂度,这就大于O(n)了

[1, 1, 2, 3, 5, 3].filter((item, index, arr) => arr.indexOf(item) < index)

或者
[1, 1, 2, 3, 5, 3].filter((item, index, arr) => arr.indexOf(item) < index && arr.lastIndexOf(item) == index)

要O(n)就只能一次遍历,而且还不能开辟额外空间,即既不能另外做一个缓存列表,也无法使用新的数组。在这种情况下,是无法完成的。
不过,O(n)不行,O(2n)却是可以的。第一步先对数组排序,第二步再比较前后项即可。

const arr = [1, 1, 2, 3, 5, 3];

for (let i = arr.sort().length - 1; 0 < i; i -= 1) {
  i -= arr.splice(i, 1)[0] === arr[i - 1];
}

console.log(arr);
var findDuplicates = function(nums) {
    const res = [];
    for (const num of nums) {
        const absNum = Math.abs(num);
        if (nums[absNum - 1] < 0) {
            res.push(absNum);
        } else {
            nums[absNum - 1] = -1 * nums[absNum - 1];
        }
    }

    return res;
};

本文地址:H5W3 » js面试题:取出数组中出现两次的值

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址