「人見人愛的A」集合差運算：排序+雙指針線性掃描

問題描述

給定兩個集合A、B，輸出屬於A但不屬於B的元素，按升序。若無則輸出NULL。多組測試，n=0且m=0結束。

算法：排序 + 雙指針合併

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

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

int main() {
    int n, m, a[101], b[101];
    while (scanf("%d %d", &n, &m) == 2 && (n || m)) {
        for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
        for (int i = 0; i < m; ++i) scanf("%d", &b[i]);

        qsort(a, n, sizeof(int), cmp);
        qsort(b, m, sizeof(int), cmp);

        int i = 0, j = 0, printed = 0;
        while (i < n) {
            if (j < m && a[i] > b[j]) ++j;           // B元素較小，推進B
            else if (j < m && a[i] == b[j]) { ++i; ++j; } // 相等，跳過(屬於B)
            else {                                     // a[i] < b[j] 或 B耗盡
                printf("%d ", a[i++]);
                printed = 1;
            }
        }
        if (!printed) printf("NULL");
        printf("\n");
    }
    return 0;
}

雙指針邏輯圖解

A: 1  3  5  7  9
B: 2  3  6  9  10
i  j  動作
0  0  1<2  → 輸出1, i=1
1  0  3>2  → j=1
1  1  3=3  → 跳過, i=2,j=2
2  2  5<6  → 輸出5, i=3
3  2  7>6  → j=3
3  3  7<9  → 輸出7, i=4
4  3  9=9  → 跳過, i=5,j=4
5  4  i==n 結束
輸出: 1 5 7

關鍵細節

• 去重：題目隱含集合無重複元素，若輸入有重複需先unique
• 邊界：j==m時，A剩餘元素全屬於差集，直接輸出
• 輸出格式：元素間單空格，行尾換行，無元素輸出NULL
• 複雜度：O(n log n + m log m) 排序主導，合併 O(n+m)

替代方案：哈希集合（數據範圍大時）

// C++ unordered_set 版
unordered_set setB(b, b+m);
for (int x : a) if (!setB.count(x)) printf("%d ", x);
// 平均 O(n+m)，需額外 O(m) 空間

C語言可手寫開放地址哈希表或用uthash.h。