如何有效率地尋找Java數組中的重複整數？

在 Java 數組中查找重複項

問題

您有一個整數數組，並且希望有效地識別任何重複項。您的初始程式碼嘗試比較每對元素，但在不存在重複項時無法準確偵測重複項。

問題

程式碼中的缺陷在於其依賴初始化的重複項標誌在所有情況下都為 false。如果沒有找到重複項，則在檢查對角線元素時（即，當 j == k 時），循環仍會將重複項設為 true。

更細緻的解決方案

要解決此問題，請確保只有在找到實際重複項時，重複項標誌才會設為 true。這可以透過在 j == k 時省略 zipcodeList[j] 與其自身的比較來實現。

這是修改後的程式碼：

duplicates = false;
for (int j = 0; j < zipcodeList.length; j++) {
    for (int k = 0; k < zipcodeList.length; k++) {
        if (k != j && zipcodeList[k] == zipcodeList[j]) {
            duplicates = true;
        }
    }
}

更快的方法

上述解決方案的運行時複雜度為O(n²)，其中n 是大批。對於大型數組，這種方法可能效率低。

檢測重複項的更有效方法是利用基於雜湊的方法，將時間複雜度降低到 O(n)。以下是使用HashSet 的範例：

boolean duplicates(int[] zipcodeList) {
    Set<Integer> lump = new HashSet<>();
    for (int zipcode : zipcodeList) {
        if (lump.contains(zipcode)) {
            return true;
        }
        lump.add(zipcode);
    }
    return false;
}

或者，可以使用boolean[] 陣列（位圖）來追蹤先前遇到的元素並在元素出現時將重複項設為true，從而實現O(n) 解決方案。第二次遇到。

結論

根據輸入陣列的大小和重複的頻率，應調整方法的選擇以最佳化效率。

以上是如何有效率地尋找Java數組中的重複整數？的詳細內容。更多資訊請關注PHP中文網其他相關文章！