我需要加速通过代码格斗测试（javascript）

任务是获取一个数组并返回最早的重复，并且如果没有返回-1。我这样写：我需要加速通过代码格斗测试（javascript）

function firstDuplicate(a) { 
    let singles = []; 

    for (let i = 0; i < a.length; i++) { 

     if (singles.indexOf(a[i]) == -1) { 
      singles.push(a[i]); 
     } 
     else { 
      return a[i]; 
     } 

    } 

    return -1; 
}

它通过除隐藏速度测试以外的所有测试。有没有另一种方式来更快地写在JS？我看到一个Java解决方案使用集合而不是数组，但我想坚持使用JS。

来源

2017-07-14 James Hamann

使用散列（一个对象）来跟踪重复项而不是另一个数组。 –

使用js对象，而不是数组。因为它是一个测验，所以不会给你答案:) – Doug

首先，你应该学习'array＃indexOf'如何工作。每次都会从起始位置到结束位置进行搜索。搜索是在'O（n）'这是非常缓慢的。有很多方法可以加快速度，它们都包括使用不同的策略/数据结构。更好的数据结构是'HashSet'（包含在'O（1）'中），'TreeSet'（包含在'O（log n）'中）。坚持数组时，更好的策略是*搜索算法*像'BinarySearch'或*排序技术*像'QuickSort'。我相信** JS **中已经有一些实现可用。 – Zabuza

您可以使用Set在JavaScript来实现这一目标还有：

function firstDuplicate(array) { 
 
    const set = new Set() 
 

 
    for (const value of array) { 
 
    if (set.has(value)) { 
 
     return value 
 
    } 
 

 
    set.add(value) 
 
    } 
 

 
    return -1 
 
} 
 

 
console.log(firstDuplicate(['a', 1, 'b', 2, 'c', 1, 2, 3]))

与解决方案的问题，如@Zabuza解释的，是你的indexOf()这改变用途算法从O（n）到O（n ）的时间复杂度，因为每个indexOf()都是O（n）。

使用Set代替Array取散列的优点，其通过使用has()从O（n）与O（1）的重复，从而把该算法返回到O（n）的总的复杂性改变你的查找时间。

来源

2017-07-14 15:51:45

你可以解释为什么这会更快。对于初学者来说，这并不明确。 'Array＃indexOf'使用的技术是什么，和'Set＃has'的区别在哪里。我认为这也会帮助OP。 – Zabuza

@Zabuza正在做这件事，现在就完成了。 –

非常感谢你解释答案。我承认目前我的头脑有点过分，但我明白你的意思。我知道这与indexOf速度有关，但我不知道你甚至可以在JS中使用Set（）。直到现在我从来没有听说过。再次感谢，我喜欢开始一天学习新事物！ –

而不是推单打只分配一个频率数组，并增加循环通过原始阵列时的频率。第一次频率是2你有最早的重复。

增加'1'时，数组中第i个元素的频率肯定会更快，然后再按一个数组，然后随时搜索数组。

来源

2017-07-14 15:49:58 pinturic

我不知道如何做到这一点，而不使用sort（）和排序在这种情况下不起作用。如果不知道之前测试的所有数字，我将如何更新频率？难道我不需要为此添加数组吗？ –

您可以使用零值预先初始化de频率数组，并在您走阵列时随时添加一个。 – pinturic

试试这个。在大型数组中没有重复的情况下，它应该给你更多的速度。

function firstDuplicate(a) { 
    let singles = new Set(a); 

    if(singles.size == a.length) 
     return -1; 

    let temp = []; 


    for (let i = 0; i < a.length; i++) { 

     if (temp.indexOf(a[i]) == -1) { 
      temp.push(a[i]); 
     } 
     else { 
      return a[i]; 
     } 

    } 
}

来源

2017-07-14 15:51:16 yBrodsky

我需要加速通过代码格斗测试（javascript）

回答

相关问题