我需要加速通過代碼格鬥測試（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）

回答

相關問題