數組去重經典算法：原地覆蓋法 C 語言實現詳解

編輯：關於C語言

問題描述

給定一個整型數組，要求僅掃描一遍（雙層循環模擬單次邏輯遍歷），將重複元素移除，保持相對順序不變，最終輸出去重後的數組。

算法核心思想：原地覆蓋法

使用雙指針思想：外層循環固定基準元素，內層循環尋找重複項，發現後將後續元素前移覆蓋，並動態縮減有效長度。

完整代碼實現

#include <stdio.h>

int main()
{
    int a[5];
    printf("input five numbers:");

    for (int i = 0; i < 5; i++) {
        scanf("%d", &a[i]);
    }

    int len = 5;  // 當前有效長度

    // 雙層遍歷：j 為基準，m 為掃描指針
    for (int j = 0; j < len; ++j) {
        for (int m = j + 1; m < len; ++m) {
            if (a[j] == a[m]) {
                // 發現重複，執行覆蓋刪除
                for (int k = m + 1; k < len; ++k) {
                    a[k - 1] = a[k];  // 後續元素前移一位
                }
                len--;      // 有效長度減 1
                --m;        // 關鍵：m 回退，因為覆蓋後當前位置是新元素，需重新比較
            }
        }
    }

    // 輸出結果
    for (int n = 0; n < len; ++n) {
        printf("%d ", a[n]);
    }
    printf("\n");

    return 0;
}

關鍵細節深度解析

1. 三層循環職責劃分

循環層	變量	職責
外層	`j`	基準元素索引，從 0 遞增到 `len-1`
中層	`m`	掃描指針，從 `j+1` 遞增，尋找與 `a[j]` 相等的元素
內層	`k`	覆蓋執行者，將 `m+1` 到末尾的元素前移一位

2. 兩個關鍵調整語句

len--;   // 刪除一個元素，邏輯長度必須同步縮減
--m;     // 覆蓋後 a[m] 位置存放的是原 a[m+1] 的值，必須重新比較，故 m 回退

為什麼要 --m？
假設數組 [5, 5, 2, 5, 5]，j=0, m=1 發現重複，覆蓋後數組變 [5, 2, 5, 5]，此時 m 位置是 2，若 m++ 會漏檢查這個 2，所以 --m 抵消外層 ++m，使下一次循環仍檢查當前位置。

3. 時間空間複雜度

時間複雜度：O(n²) —— 雖然要求「掃描一遍」，但雙層循環本質仍是平方級
空間複雜度：O(1) —— 原地操作，無額外空間
穩定性：穩定 —— 相對順序保持不變

測試驗證

輸入：5 5 2 5 5
過程：
j=0: 基準 5
  m=1: 發現 5 -> 覆蓋 -> [5,2,5,5] len=4 m回退到0 -> m++變1
  m=1: 比較 2 != 5
  m=2: 比較 5 == 5 -> 覆蓋 -> [5,2,5] len=3 m回退到1 -> m++變2
  m=2: 循環結束
j=1: 基準 2
  m=2: 比較 5 != 2
j=2: 基準 5, 無後續元素

輸出：5 2