C語言集合運算：求集合差集 A-B 完整實現

編輯：關於C語言

問題描述

輸入兩個集合 A（大小 n）和 B（大小 m），輸出屬於 A 但不屬於 B 的元素，按升序排列。若無元素輸出 NULL。多組測試，n=m=0 結束。元素範圍未指定，假設為 32 位整數。

算法方案比較

方法	時間複雜度	空間	適用場景
排序+雙指針	O(n log n + m log m)	O(1) 額外	通用、無重複元素
哈希集合	O(n+m) 平均	O(m)	大數據、查找頻繁
位圖	O(n+m)	O(範圍)	元素範圍小(如 0-10⁶)

原始代碼：排序+嵌套循環

原代碼對 A、B 分別排序（冒泡 O(n²)），再對 A 中每個元素線性掃描 B 判斷是否存在。總複雜度 O(n² + m² + n×m)，效率極低。

優化版：qsort + 二分查找 / 雙指針

#include <stdio.h>
#include <stdlib.h>

int cmp(const void *a, const void *b) { return *(int*)a - *(int*)b; }

int main() {
    int n, m;
    while (scanf("%d %d", &n, &m) == 2 && (n || m)) {
        int *A = malloc(n * sizeof(int));
        int *B = malloc(m * sizeof(int));
        for (int i=0; i A[i]) { // A[i] 不在 B 中
                if (!first) putchar(' ');
                printf("%d", A[i]);
                first = false;
            }
            // 跳過 A 中重複元素（若輸入可能重複）
            int cur = A[i];
            while (i < n && A[i] == cur) i++;
        }
        if (first) printf("NULL");
        putchar('\n');
        free(A); free(B);
    }
    return 0;
}

關鍵優化點

qsort 替代冒泡：O(n log n) vs O(n²)，標準庫高度優化。
雙指針單掃描：利用有序性，i、j 只前進不後退，合併階段 O(n+m)。
去重處理：輸出時跳過 A 中連續相同值，符合集合語義。
動態分配：根據 n,m 分配記憶體，避免固定大小陣列浪費/越界。

進階：哈希集合實現（C 無內建，手寫開放地址法）

// 簡易哈希表，負載因子 0.5，線性探測
#define HSIZE 200003
int hset[HSIZE]; char hused[HSIZE];
void hclear() { memset(hused, 0, HSIZE); }
void hinsert(int x) { int p=(x%HSIZE+HSIZE)%HSIZE; while(hused[p]) p=(p+1)%HSIZE; hset[p]=x; hused[p]=1; }
bool hfind(int x) { int p=(x%HSIZE+HSIZE)%HSIZE; while(hused[p]) { if(hset[p]==x) return true; p=(p+1)%HSIZE; } return false; }

適用於 n,m ~ 10⁵ 且元素分佈均勻的場景。