在线性时间内，在长度为 N、数字 1 到 N-1 的数组中查找重复项，而无需使用额外的 obj/arr 来跟踪计数

Question

我能够在线性时间和 space 内完成这个 edabit 挑战，但挑战说它只能使用相同的数组完成（不需要额外的 obj/arr 来保持跟踪'already seen' 个数字。）和 线性时间 。

约束：长度为'n'且数字范围为1到n-1

的列表

// length N
// 1 to N - 1
const l = [5, 2, 1, 3, 4, 2]

function findDuplicate(list) {
  
}

我认为这与在数组中的索引处跟踪数字 'already seen' 有关，但我不能完全做到这一点而无需再次遍历数组。

我是这样做到的：

function findDuplicate(list) {
  const dict = {}
  for (let i=0; i < list.length; i++) {
    dict[list[i]] = dict[list[i]] + 1 || 1   
    if (dict[list[i]] === 2) return list[i]
  }
}

但我正在使用 obj 来跟踪“已经看过”的号码。

Answer 1

const numbers = [5, 2, 1, 3, 4, 2];
const n = numbers.length - 1;
const expectedSum = (n * (n + 1)) / 2;
const sum = numbers.reduce((acc, val) => acc + val, 0);
const duplicate = sum - expectedSum ;

Answer 2

因为你有一个自然数数组，只有一个重复，你可以得到直到 n-1 的自然数之和，然后从数组元素的总和中减去它。

(5 + 2 + 1 + 3 + 4 + 2) - (1 + 2 + 3 + 4 + 5) = 2

这是一个片段：

function findDuplicate(list) {
  const n = list.length,
        sum = list.reduce((a, b) => a + b, 0),
        naturalSum = n * (n-1) / 2

  return sum - naturalSum
}

console.log( findDuplicate([5, 2, 1, 3, 4, 2]) )
console.log( findDuplicate([1, 2, 3, 4, 3]) )

如果不允许，您也可以在不使用额外变量的情况下编写它：

function findDuplicate(l) {
  return l.reduce((a, b) => a + b, 0) - (l.length * (l.length - 1) / 2)
}

Answer 3

也许[5, 2, 1, 3, 4, 2].reduce((acc, num, index) => (acc + num) - index, 0)

在线性时间内，在长度为 N、数字 1 到 N-1 的数组中查找重复项，而无需使用额外的 obj/arr 来跟踪计数

Find, in linear time, duplicate in array of length N, numbers 1 to N-1 without using additional obj/arr to keep track of a count

javascript

arrays

duplicates