C++ 陣列去重實戰：排序 + 雙指針原地刪除

問題描述

給定一個無序整數陣列，移除其中重複元素，返回去重後的新長度。面試常見題目，要求原地修改陣列、空間複雜度 O(1)。

解決思路

1. 先排序：將相同元素聚集相鄰。
2. 雙指針掃描：i 遍歷陣列，j 指向下一個不重複元素的存放位置。遇到相鄰相等時移動 i 跳過重複，將不重複值寫入 j 並推進 j。

時間複雜度：排序 O(n log n) + 掃描 O(n) = O(n log n)。空間複雜度：O(1)（原地修改）。

完整可編譯範例（C++17）

#include 
#include   // std::sort, std::swap

// 通用列印函數
template
void printArray(const T arr[], int size) {
    for (int i = 0; i < size - 1; ++i) std::cout << arr[i] << ", ";
    std::cout << arr[size-1] << '\n';
}

// 選擇排序（教學用，實際建議用 std::sort）
template
void selectionSort(T arr[], int size) {
    for (int i = 0; i < size - 1; ++i) {
        int minIdx = i;
        for (int j = i + 1; j < size; ++j)
            if (arr[j] < arr[minIdx]) minIdx = j;
        if (minIdx != i) std::swap(arr[i], arr[minIdx]);
    }
}

// 去重：要求陣列已排序
template
int removeDuplicates(T arr[], int size) {
    if (size == 0) return 0;
    int j = 0;
    for (int i = 0; i < size - 1; ++i) {
        while (i < size - 1 && arr[i] == arr[i+1]) ++i;  // 跳過重複
        arr[j++] = arr[i];
    }
    arr[j++] = arr[size-1];  // 處理最後一個元素
    return j;
}

int main() {
    int data[] = {9, 1, 1, 8, 2, 3, 3, 4, 3, 3, 5, 9, 7, 8, 2, 6, 9, 1, 9, 0, 9, 0};
    int n = sizeof(data) / sizeof(int);

    std::cout << "原始陣列: "; printArray(data, n);

    selectionSort(data, n);  // 實際專案請用 std::sort(data, data+n);
    std::cout << "排序後: "; printArray(data, n);

    n = removeDuplicates(data, n);
    std::cout << "去重後: "; printArray(data, n);

    return 0;
}

關鍵細節解析

• while (arr[i] == arr[i+1]) ++i; 將 i 移動到當前重複群組的最後一個元素。
• arr[j++] = arr[i]; 將該群組代表值寫入前端。
• 迴圈結束後單獨處理最後一個元素（因迴圈條件 i < size-1 會漏掉）。
• 返回值 j 即為新長度，呼叫端可用此長度截取有效區間。

現代 C++ 更佳寫法

#include 
#include 

std::vector vec = {9,1,1,8,2,3,3,4,3,3,5,9,7,8,2,6,9,1,9,0,9,0};
std::sort(vec.begin(), vec.end());
vec.erase(std::unique(vec.begin(), vec.end()), vec.end());
// vec 即為去重後結果，自動管理記憶體

std::unique 將不重複元素前移並返回新邏輯結尾迭代器，配合 erase 實現真正刪除。這是生產代碼推薦做法。

面試加分點

1. 說明為何先排序：將去重問題轉為「移除相鄰重複」問題。
2. 討論若不能改變元素順序，需用 std::unordered_set 輔助（O(n) 時間、O(n) 空間）。
3. 指出選擇排序教學用，實際應用 std::sort（內省排序，平均 O(n log n)）。
4. 邊界條件處理：空陣列、單元素陣列、全重複陣列。