C++ 實戰：兩個整數集合求並集算法實現與代碼優化

求兩個整數陣列的並集 (去重合併) 是基礎算法高頻考點。本文提供基於雙重循環的經典實現、STL `std::set`/`std::vector` 現代化解法、以及針對有序/無序數據的優化策略，附完整可編譯代碼。

問題定義

• 輸入：兩個整數陣列 `a` (長度 `an`)、`b` (長度 `bn`)，**假設陣列內部無重複元素** (若有需先去重)。
• 輸出：合併後不重複元素組成的陣列 `r` 及其長度 `n`。
• 要求：不修改原陣列順序 (可選)，時間複盡度盡可能低。

方案一：雙重循環暴力法 (教學經典，O(an * bn))

適用於小規模數據、面試手寫、無序陣列且不可排序場景。

#include 
#include  // memcpy
using namespace std;

void arrUnion(const int a[], const int b[], int r[], int an, int bn, int* n) {
    // 1. 複製 a 到 r
    *n = an;
    memcpy(r, a, an * sizeof(int));
    
    // 2. 遍歷 b，檢查是否已在 r 中
    for (int i = 0; i < bn; ++i) {
        bool found = false;
        for (int j = 0; j < *n; ++j) { // 注意：j < *n (動態長度)
            if (r[j] == b[i]) { found = true; break; }
        }
        if (!found) {
            r[*n] = b[i];
            (*n)++;
        }
    }
}

int main() {
    int a[10] = {1,2,3,4,5,6,7,8,9,10};
    int b[10] = {3,4,5,6,7,8,10,11,8,3}; // b 內部有重複，邏輯仍正確
    int c[20]; // 足夠大
    int n = 0;
    
    arrUnion(a, b, c, 10, 10, &n);
    
    cout << "並集大小: " << n << endl;
    for (int i = 0; i < n; ++i) cout << c[i] << ' ';
    cout << endl;
    return 0;
}
// 輸出: 1 2 3 4 5 6 7 8 9 10 11 (大小 11)

方案二：STL `std::set` 自動去重 (現代 C++ 首選，O((an+bn) log(an+bn)))

#include 
#include 
#include 
#include 
using namespace std;

vector unionSet(const vector& a, const vector& b) {
    set s(a.begin(), a.end()); // 自動去重、有序
    s.insert(b.begin(), b.end());
    return vector(s.begin(), s.end()); // 轉回 vector
}

int main() {
    vector a = {1,2,3,4,5,6,7,8,9,10};
    vector b = {3,4,5,6,7,8,10,11,8,3};
    vector res = unionSet(a, b);
    for (int x : res) cout << x << ' '; // 1 2 3 4 5 6 7 8 9 10 11
    return 0;
}

方案三：有序陣列雙指針合併 (最優 O(an+bn)，需預先排序)

vector unionSorted(vector a, vector b) { // 值傳遞可直接排序
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    a.erase(unique(a.begin(), a.end()), a.end()); // 去重
    b.erase(unique(b.begin(), b.end()), b.end());
    
    vector res;
    res.reserve(a.size() + b.size());
    size_t i = 0, j = 0;
    while (i < a.size() && j < b.size()) {
        if (a[i] < b[j]) res.push_back(a[i++]);
        else if (a[i] > b[j]) res.push_back(b[j++]);
        else { res.push_back(a[i]); ++i; ++j; } // 相等取一
    }
    while (i < a.size()) res.push_back(a[i++]);
    while (j < b.size()) res.push_back(b[j++]);
    return res;
}

方案四：`std::unordered_set` 平均 O(1) 查找 (大規模無序數據首選)

#include 
vector unionFast(const vector& a, const vector& b) {
    unordered_set s;
    s.reserve(a.size() + b.size()); // 預分配避免重哈希
    for (int x : a) s.insert(x);
    for (int x : b) s.insert(x);
    return vector(s.begin(), s.end()); // 無序
}

複雜度與選型指南

總結

**面試手寫用雙重循環展示邏輯基本功；工程實戰首選 `std::set`/`unordered_set` 一行式解決。** 理解各方案複雜度權衡、輸出順序特性、STL 容器特性，才能根據業務數據量級、有序需求、環境約束做出最優架構決策。