hdu2034 差集

人见人爱A-B

http://acm.hdu.edu.cn/showproblem.php?pid=2034

Problem Description
参加过上个月月赛的同学一定还记得其中的一个最简单的题目，就是{A}+{B}，那个题目求的是两个集合的并集，今天我们这个A-B求的是两个集合的差，就是做集合的减法运算。（当然，大家都知道集合的定义，就是同一个集合中不会有两个相同的元素，这里还是提醒大家一下）

呵呵，很简单吧？

Input
每组输入数据占1行,每行数据的开始是2个整数n(0<=n<=100)和m(0<=m<=100),分别表示集合A和集合B的元素个数，然后紧跟着n+m个元素，前面n个元素属于集合A，其余的属于集合B. 每个元素为不超出int范围的整数,元素之间有一个空格隔开.
如果n=0并且m=0表示输入的结束，不做处理。

Output
针对每组数据输出一行数据,表示A-B的结果,如果结果为空集合，则输出“NULL”,否则从小到大输出结果,为了简化问题，每个元素后面跟一个空格.

Sample Input
3 3 1 2 3 1 4 7
3 7 2 5 8 2 3 4 5 6 7 8
0 0

Sample Output
2 3
NULL

解题思路：
差集：给两个集合A和B，A-B的差集是（x属于A，但不属于B）。
注意输出要求元素从小到大的顺序，提示要做升序排序。

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

int main (int argc, char const* argv[])
{
    int n, m, i, j, t, null_flg;
    int a[100], b[100];

    while (1) {
        scanf("%d %d", &n, &m);
        if (n == 0 && m == 0) break;

        for (i = 0; i < n; i++) {
            scanf("%d", &a[i]);
        }
        for (i = 0; i < m; i++) {
            scanf("%d", &b[i]);
        }

        // 元素个数小于100，先选择法排序
        for (i = 0; i < n-1; i++) {
            for (j = i+1; j < n; j++) {
                if (a[i] > a[j]) {
                    t = a[i];
                    a[i] = a[j];
                    a[j] = t;
                }
            }
        }
        for (i = 0; i < m-1; i++) {
            for (j = i+1; j < m; j++) {
                if (b[i] > b[j]) {
                    t = b[i];
                    b[i] = b[j];
                    b[j] = t;
                }
            }
        }

        i = 0; j = 0;
        null_flg = 1;
        while (i < n && j < m) {
            // 当a元素比b小时，肯定不在b中，属于差集元素
            // i++有可能让i越界，所以加上i<n
            while (a[i] < b[j] && i < n) {
                printf("%d ", a[i]); i++;
                null_flg = 0;
            }
           
            // 当a元素比b大时，j++移动指针，直到a元素小于等于b元素
            // j++有可能让j越界，所以加上j<m
            while (a[i] > b[j] && j < m) {
                j++;
            }

            // 当a元素和b元素相等时，不属于差集
            // i和j都加1，移动指针到后一个元素
            // 整个循环加上i<n && j<m
            if (a[i] == b[j]) {
                i++; j++;
            }
        }

        // 如果a集合有剩下未被处理的元素，则都属于差集
        while (i < n) {
            printf("%d ", a[i]); i++;
            null_flg = 0;
        }
       
        // 当没有任何输出，证明差集是空集
        if (null_flg) printf("NULL");

        // 多个测试用例时，添加换行符
        printf("\n");
    }

    return 0;
}