为codefighters javascript firstDuplicate()函数加速此代码

Question

每个Codefighters:

注意:编写具有O(n)时间复杂度和O(1)额外空间复杂度的解决方案,因为这是您在真实访谈期间要求做的事情.

给定一个仅包含1到a.length范围内的数字的数组a,找到第二个匹配项具有最小索引的第一个重复数字.换句话说,如果有多于1个重复的数字,则返回第二次出现的索引小于另一个出现的第二次出现的索引的数量.如果没有这样的元素,则返回-1.

例

对于a = [2,3,3,1,5,2],输出应为firstDuplicate(a)= 3.

有2个重复:数字2和3.第二次出现3的索引小于第二次出现的2,所以答案是3.

对于a = [2,4,3,5,1],输出应为firstDuplicate(a)= -1.

---

所以这就是我想出来的.它工作但最终测试失败,因为它运行超过4000毫秒.我不知道我还能做些什么.有什么提高速度的想法吗？

function firstDuplicate(a) {
    var test   = [],
        lowest = undefined;

    for (var i=0; i<a.length; i++) {
        if (test.indexOf(a[i]) > -1) {
            lowest = lowest || i;
            if (i < lowest) {
                lowest = i;
            }
        }
        else {
            test.push(a[i]);
        }
    }

    return lowest ? a[lowest] : -1;
}

---

这是我的第二次尝试,但在最后一次测试中仍未通过......

function firstDuplicate(a) {
    var low = undefined,
        last = -1;

    for (var i=0; i<a.length; i++) {
        last = a.lastIndexOf(a[i])
        if (last > i && (low === undefined || last < low)) {
            low = last;
        }
    }

    return low !== undefined ? a[low] : -1;
}

Answer 1

这些要求提供了如何解决这个问题的线索.数组中包含的数字集必须与以下标准匹配:

只有1到a.length范围内的数字

换句话说,只有正数小于或等于数组的长度.如果数组包含十个数字,则它们都不会大于10.

凭借这种洞察力,我们有了一种跟踪我们已经看到过的数字的方法.我们可以将数字本身视为数组的索引,修改该索引处的元素(在这种情况下使其为负数),如果我们遇到相同的数字并且该索引处的元素小于零,那么我们就知道了见过它.

console.clear()
const test1 = [2, 3, 3, 1, 5, 2]
const test2 = [2, 4, 3, 5, 1]


function firstDuplicate(a) {
  for (let i of a) {
    let posi = Math.abs(i) - 1
    if (a[posi] < 0) return posi + 1
    a[posi] = a[posi] * -1
  }

  return -1
}

console.log(firstDuplicate(test1))
console.log(firstDuplicate(test2))
console.log(firstDuplicate([2,2]))
console.log(firstDuplicate([2,3,3]))
console.log(firstDuplicate([3,3,3]))

原始不正确的答案

跟踪已经看过的数字并返回之前看过的第一个数字.

console.clear()
const test1 =   [2, 3, 3, 1, 5, 2]
const test2 = [2, 4, 3, 5, 1]

      
function firstDuplicate(a){
  const seen = {}
  for (let v of a){
    if (seen[v]) return v
    seen[v] = v
  }
  
  return -1
}

console.log(firstDuplicate(test1))
console.log(firstDuplicate(test2))

然而,正如评论中所指出的,这个答案需要额外的O(n)空间,而不是O(1)额外的空间.

Answer 2

我们将利用数组a仅包含 1 到 范围内的数字a.length这一事实，记住通过反转数组中该位置的任何符号的符号已经看到了一个值。

function lowestDuplicate(arr) {

  for (let i = 0; i < arr.length; i++) {
    const val = Math.abs(arr[i]);
    if (arr[val - 1] < 0) return val;
    arr[val - 1] = -arr[val - 1];
  }
  return -1;
}

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