如何在不使用集合的情況下有效地從數組中刪除重複項？

無需借助Set 即可高效地從數組中刪除重複項

您已努力創建一個自定義解決方案來從數組中刪除重複元素，但效能瓶頸已經出現。為了優化此實現，我們將分析您的方法的缺點並提出替代策略。

分析您的演算法

您的演算法嘗試透過比較每個值來搜尋重複項元素與每個後續元素。這種詳盡的比較導致時間複雜度為 O(n^2)。對於大型數組，此策略可能變得極為低效。

最佳化方法

為了顯著提高效能，我們可以考慮以下最佳化：

1. 利用雜湊映射：實作雜湊映射來儲存迭代過程中遇到的唯一元素。將每個元素新增至陣列時，檢查它是否已作為雜湊映射中的鍵存在。如果沒有，請添加。這種方法可以實現高效的恆定時間查找操作，將時間複雜度降低到 O(n)。
2. 過濾前排序： 依升序對陣列進行排序。現在，重複的元素將彼此相鄰。迭代已排序的陣列並消除相鄰的重複項，從而得到線性時間 O(n) 演算法。

替代解決方案

雖然上述最佳化可以為了提高演算法的效能，您也可以考慮其他已建立的技術：

• 設定集合：由於您需要避免使用Set，因此我們不會深入研究此選項。
• 使用排序集合：與濾波前排序類似，利用排序集合，例如TreeSet 或 NavigableSet。它自動維護排序順序並允許高效的元素檢索，從而導致 O(n log n) 複雜度。

實作

基於最佳化方法，使用雜湊映射的演算法的修改版本可能是：

public static int[] removeDuplicatesWithoutSet(int[] arr) {

    HashMap<Integer, Boolean> map = new HashMap<>();
    int end = arr.length;

    for (int i = 0; i < end; i++) {
        if (map.containsKey(arr[i])) {
            int shiftLeft = i;
            for (int k = i + 1; k < end; k++, shiftLeft++) {
                arr[shiftLeft] = arr[k];
            }
            end--;
            i--;
        } else {
            map.put(arr[i], true);
        }
    }

    int[] whitelist = new int[end];
    for (int i = 0; i < end; i++) {
        whitelist[i] = arr[i];
    }
    return whitelist;
}

以上是如何在不使用集合的情況下有效地從數組中刪除重複項？的詳細內容。更多資訊請關注PHP中文網其他相關文章！