求两个集合交集 （C语言代码）

解题思路:

     先将集合A、B的元素升序排列，然后使用i，j两指针逐个比对集合A、B的元素取交集，结果也为升序。

     示意图：（求交集C）

参考代码:

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

#define MAX 1000

int cmp(const void *a, const void *b) {

	return *(int *)a - *(int *)b;
}

int main()
{
	int n, m, i, j, k;
	int A[MAX], B[MAX], C[MAX];

	scanf("%d%d", &n, &m);

	for (i = 0; i < n; i++) {

		scanf("%d", &A[i]);
	}
	qsort(A, n, sizeof(A[0]), cmp); // 集合A元素升序排列

	for (i = 0; i < m; i++) {

		scanf("%d", &B[i]);
	}
	qsort(B, m, sizeof(B[0]), cmp); // 集合B元素升序排列

	for (i = 0, j = 0, k = 0; i < n && j < m; ) { // i、j任一指针遍历完集合时结束循环

		if (A[i] == B[j]) { // 当i, j两指针指向元素相等

			C[k++] = A[i]; // 元素进交集C
			i++;
			j++; // 两指针均移动
		}
		else {

			A[i] < B[j] ? i++ : j++; // 指向元素小的指针移动
		}
	}

	if (k) printf("%d", C[0]);
	for (i = 1; i < k; i++) { // 输出交集C

		printf(" %d", C[i]);
	}
	return 0;
}