如何高效移除数组重复项并满足指定约束与结果要求？

核心思路 #

要满足保持唯一元素首次出现顺序、重复项移至数组末尾，同时符合时间复杂度≤O(n log n)、额外空间≤O(n)的约束，我们可以通过以下步骤实现：

• 用集合记录已保留的唯一元素，避免重复；
• 遍历数组时，将首次出现的元素放到数组前半段，重复元素暂存到临时列表；
• 遍历结束后，把临时列表中的重复元素依次追加到数组后半段。

具体实现步骤 #

1. 初始化一个集合（哈希集合或有序集合）、一个临时列表存储重复元素，以及一个指针标记当前唯一元素的存放位置；
2. 遍历原数组：
   • 若当前元素未在集合中，将其放到指针位置，指针后移，并将元素加入集合；
   • 若元素已存在，将其加入重复元素列表；
3. 把重复元素列表中的元素依次写入数组指针开始的位置，完成数组更新。

代码示例（C++） #

哈希集合版本（平均时间O(n)）

#include <iostream>
#include <unordered_set>
#include <vector>

void moveDuplicatesToEnd(int A[], int n) {
    std::unordered_set<int> seen;
    std::vector<int> duplicates;
    int uniquePtr = 0;

    for (int i = 0; i < n; ++i) {
        if (seen.find(A[i]) == seen.end()) {
            seen.insert(A[i]);
            A[uniquePtr++] = A[i];
        } else {
            duplicates.push_back(A[i]);
        }
    }

    // 将重复元素追加到数组末尾
    for (int num : duplicates) {
        A[uniquePtr++] = num;
    }
}

int main() {
    int A[] = {2,3,7,3,2,11,2,3,1,15};
    int n = sizeof(A) / sizeof(A[0]);

    moveDuplicatesToEnd(A, n);

    // 打印结果
    for (int i = 0; i < n; ++i) {
        std::cout << A[i] << " ";
    }
    std::cout << std::endl;
    // 输出示例：2 3 7 11 1 15 3 2 2 3 
    return 0;
}

有序集合版本（最坏时间O(n log n)）

如果担心哈希冲突导致最坏时间复杂度超标，可以改用有序集合，保证严格符合O(n log n)的要求：

#include <iostream>
#include <map>
#include <vector>

void moveDuplicatesToEnd(int A[], int n) {
    std::map<int, bool> seen;
    std::vector<int> duplicates;
    int uniquePtr = 0;

    for (int i = 0; i < n; ++i) {
        if (seen.find(A[i]) == seen.end()) {
            seen[A[i]] = true;
            A[uniquePtr++] = A[i];
        } else {
            duplicates.push_back(A[i]);
        }
    }

    for (int num : duplicates) {
        A[uniquePtr++] = num;
    }
}

复杂度分析 #

• 时间复杂度：哈希集合版本平均O(n)，有序集合版本O(n log n)，均满足题目≤O(n log n)的约束；
• 空间复杂度：集合最多存储n个唯一元素，临时列表最多存储n-1个重复元素，额外空间总计O(n)，符合要求。

内容的提问来源于stack exchange，提问作者artur anikin