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

Question

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

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

如输入［1, 1, 2, 3, 5, 3］返回 ［1, 3］

Answer 1

看了一下，最好的是 @madRain 的解法。
然后又仔细读了下题。要求只找出出现过两次的项。在此题中还有一个已知的限定条件，重复的项最多只会出现2次。所以 @madRain 的解法是最优的。如果没有这个已知项，那是无论如何也无法在O(n)中判断出的，当找出重复项时并不知道后续是否还有重复项，只有在有顺序的数组中才能在一次中完成判断，所以至少要O(2n)。而正因为此题有了这个限定条件，所以可以实现O(n)

---

要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);