Java 陣列去重演算法：noDups 原地移除重複元素

演算法前提條件

**陣列必須已排序**。此演算法利用有序特性，僅比較相鄰元素即可識別重複值，達到 O(n) 時間複雜度、O(1) 空間複雜度的原地去重。

核心邏輯

public static void noDups(int[] arr) {
    if (arr == null || arr.length <= 1) return;
    
    int writeIndex = 0;  // 寫入位置指標
    
    for (int i = 0; i < arr.length - 1; i++) {
        // 當前元素與下一個元素不同，保留當前元素
        if (arr[i] != arr[i + 1]) {
            arr[writeIndex++] = arr[i];
        }
    }
    
    // 處理最後一個元素 (迴圈未比較到)
    arr[writeIndex++] = arr[arr.length - 1];
    
    // 截斷陣列 (Java 陣列長度固定，實際使用時需配合長度資訊)
    // 實務上常回傳新長度，或轉為 List/新陣列
}

執行流程圖解

輸入陣列：[1, 1, 2, 2, 2, 3, 4, 4, 5]

完整可執行範例

public class ArrayDeduplication {
    
    // 回傳去重後的有效長度
    public static int noDups(int[] arr) {
        if (arr == null || arr.length <= 1) return arr.length;
        
        int writeIndex = 0;
        for (int i = 0; i < arr.length - 1; i++) {
            if (arr[i] != arr[i + 1]) {
                arr[writeIndex++] = arr[i];
            }
        }
        arr[writeIndex++] = arr[arr.length - 1];
        return writeIndex;
    }
    
    public static void main(String[] args) {
        int[] sortedArray = {1, 1, 2, 2, 2, 3, 4, 4, 5, 5, 5, 6};
        
        int newLength = noDups(sortedArray);
        
        System.out.print("去重結果: ");
        for (int i = 0; i < newLength; i++) {
            System.out.print(sortedArray[i] + " ");
        }
        // 輸出: 1 2 3 4 5 6
    }
}

複雜度分析

• 時間複雜度：O(n) - 單次掃描
• 空間複雜度：O(1) - 原地修改，無額外空間
• 穩定性：穩定 (保持元素相對順序)

擴展：未排序陣列去重

若陣列未排序，常見方案：

1. 先排序再去重：O(n log n) + O(n) = O(n log n)
2. HashSet 過濾：O(n) 時間，O(n) 空間，不保持順序
3. LinkedHashSet：O(n) 時間，O(n) 空間，**保持插入順序**

// 保持順序去重 (未排序陣列)
public static int[] deduplicateUnsorted(int[] arr) {
    return Arrays.stream(arr)
                 .boxed()
                 .collect(Collectors.toCollection(LinkedHashSet::new))
                 .stream()
                 .mapToInt(Integer::intValue)
                 .toArray();
}

總結

noDups 是**有序陣列去重的最優解**，體現「有序性」這一關鍵資訊的算法價值。面試常考察：辨識前提條件、雙指標技巧、邊界處理 (最後一個元素)。