如何求两个数组的交集c使用c语言

### C语言实现两个数组交集算法 在C语言中，可以通过多种方法来计算两个数组的交集。以下是几种常见的解决方案及其详细解释。 #### 方法一：双指针法 这种方法适用于已排序的数组。通过比较两个数组中的元素大小逐步移动指针，找到相同的元素并打印出来。 ```c #include <stdio.h> void intersection(int arr1[], int arr2[], int len1, int len2) { int i = 0, j = 0; while (i < len1 && j < len2) { if (arr1[i] < arr2[j]) { i++; } else if (arr1[i] > arr2[j]) { j++; } else { printf("%d ", arr1[i]); i++; j++; } } } int main() { int arr1[] = {1, 2, 3, 4, 5}; int arr2[] = {3, 4, 5, 6, 7}; int len1 = sizeof(arr1) / sizeof(arr1[0]); int len2 = sizeof(arr2) / sizeof(arr2[0]); intersection(arr1, arr2, len1, len2); return 0; } ``` 此代码假设输入数组已经按升序排列[^1]。如果未排序，则需先对其进行排序操作。 --- #### 方法二：基于`qsort`函数的双指针法 当输入数组可能无序时，可以利用标准库中的`qsort`函数对数组进行排序后再执行双指针逻辑。 ```c #include <stdio.h> #include <stdlib.h> // 定义用于qsort的比较函数 int cmp(const void *a, const void *b) { return (*(int *)a - *(int *)b); } int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) { qsort(nums1, nums1Size, sizeof(int), cmp); qsort(nums2, nums2Size, sizeof(int), cmp); int i = 0, j = 0, k = 0; int prev = INT_MIN; // 动态分配返回数组的最大长度 int min_size = (nums1Size < nums2Size) ? nums1Size : nums2Size; int* result = (int*)malloc(min_size * sizeof(int)); while (i < nums1Size && j < nums2Size) { if (nums1[i] < nums2[j]) { i++; } else if (nums1[i] > nums2[j]) { j++; } else { if (prev != nums1[i]) { // 去重 result[k++] = nums1[i]; prev = nums1[i]; } i++; j++; } } *returnSize = k; return result; } int main() { int nums1[] = {4, 9, 5}; int nums2[] = {9, 4, 9, 8, 4}; int nums1Size = sizeof(nums1) / sizeof(nums1[0]); int nums2Size = sizeof(nums2) / sizeof(nums2[0]); int returnSize; int* res = intersection(nums1, nums1Size, nums2, nums2Size, &returnSize); for (int i = 0; i < returnSize; ++i) { printf("%d ", res[i]); } free(res); // 释放动态内存 return 0; } ``` 这段代码实现了去重功能，并支持任意顺序的输入数组[^2]。 --- #### 方法三：暴力匹配法 对于较小规模的数据集，可以直接遍历其中一个数组，在另一个数组中逐一查找是否存在相等项。该方法时间复杂度较高（O(n*m)），适合简单场景。 ```c #include <stdio.h> #include <stdbool.h> bool contains(int array[], int size, int value) { for (int i = 0; i < size; i++) { if (array[i] == value) return true; } return false; } int* findIntersection(int nums1[], int nums1Size, int nums2[], int nums2Size, int* returnSize) { int maxSize = (nums1Size < nums2Size) ? nums1Size : nums2Size; int* result = malloc(maxSize * sizeof(int)); int count = 0; bool isDuplicate; for (int i = 0; i < nums1Size; i++) { isDuplicate = false; if (!contains(result, count, nums1[i])) { // 防止重复插入 if (contains(nums2, nums2Size, nums1[i])) { result[count++] = nums1[i]; } } } *returnSize = count; return result; } int main() { int nums1[] = {1, 2, 2, 1}; int nums2[] = {2, 2}; int nums1Size = sizeof(nums1) / sizeof(nums1[0]); int nums2Size = sizeof(nums2) / sizeof(nums2[0]); int returnSize; int* res = findIntersection(nums1, nums1Size, nums2, nums2Size, &returnSize); for (int i = 0; i < returnSize; i++) { printf("%d ", res[i]); } free(res); return 0; } ``` 这种方案虽然直观易懂，但在大规模数据下效率较低[^4]。 --- #### 性能对比分析 | **方法** | **优点** | **缺点** | |------------------|-----------------------------------|--------------------------| | 双指针法 | 时间复杂度低 O(m+n)，空间占用少 | 输入必须提前排序 | | `qsort`+双指针法 | 自动处理乱序情况 | 排序增加了额外开销 O(nlogn) | | 暴力匹配法 | 编写容易 | 效率低下 | 推荐优先考虑前两种方式以获得更好的性能表现。 ---