优化查找不同大小数组公共元素的C语言代码及返回数组长度问题

现有代码存在的问题 #

你提到的“4层循环”本质是两次独立的双层遍历，总时间复杂度为O(2nm)，除此之外还有几个隐性问题：

• 函数末尾的free(common_elements);写在return之后，永远不会执行，而且你需要把堆地址返回给调用方，本来就不能在函数内部释放，需要调用方用完后手动释放，否则会内存泄漏
• 没有处理重复元素的场景：如果同一个元素在第一个数组出现多次、或者在第二个数组出现多次，会被重复计数多次，不符合普通交集的需求（交集默认是去重的，如果要保留重复属于可选项需要特殊处理）
• 调用方手动写死循环长度3，完全依赖输入数组的交集长度，换输入就会越界

代码优化方案 #

时间复杂度优化 #

有两种常用的优化思路，比原方案效率高很多：

• 排序+双指针法，时间复杂度O(nlogn + mlogm)，适合数组规模较大的场景
  操作步骤：先对两个数组做排序，再用两个指针分别从两个数组头部遍历：
  1. 两个指针指向的元素相等时，就是公共元素，存入结果，同时移动两个指针
  2. 哪边元素更小，就移动哪边的指针
  3. 整个过程只需要一次遍历就能完成计数和存储，不需要走两次双层循环
• 哈希集合法，时间复杂度O(n+m)，是效率最高的方案
  操作步骤：先把长度更小的数组的元素存入哈希集合，再遍历长度更大的数组，碰到存在于哈希集合中的元素就是公共元素，一次遍历即可完成

返回数组大小的解决方案 #

C语言无法直接返回带长度的数组，业内常用两种方案解决越界问题：

• 新增输出参数：函数定义增加一个int *res_size的指针参数，函数内部把交集的长度写入该指针指向的内存地址，调用方拿到这个长度后再遍历，完全不会越界
• 哨兵标记：如果你的业务场景中数组元素都是正整数，可以约定返回数组的最后一位存入-1作为结束标记，调用方遍历到-1就终止循环，不需要提前知道长度

优化后完整代码示例（排序+双指针+输出参数方案） #

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

// 排序用的比较函数，供qsort调用
int cmp(const void *a, const void *b) {
    return *(int*)a - *(int*)b;
}

// 新增res_size参数用来返回结果数组的长度
int *f(int first[], int second[], int size_first, int size_second, int *res_size) {
    // 先对两个数组排序
    qsort(first, size_first, sizeof(int), cmp);
    qsort(second, size_second, sizeof(int), cmp);

    int i = 0, j = 0, count = 0;
    // 第一次遍历统计公共元素数量，自动去重
    while (i < size_first && j < size_second) {
        if (first[i] == second[j]) {
            count++;
            // 跳过重复元素
            int cur = first[i];
            while (i < size_first && first[i] == cur) i++;
            while (j < size_second && second[j] == cur) j++;
        } else if (first[i] < second[j]) {
            i++;
        } else {
            j++;
        }
    }

    // 申请内存，增加空判断避免内存申请失败
    int *common_elements = (int*)malloc(count * sizeof(int));
    if (common_elements == NULL) {
        *res_size = 0;
        return NULL;
    }

    // 第二次遍历存储公共元素
    i = 0, j = 0;
    int k = 0;
    while (i < size_first && j < size_second) {
        if (first[i] == second[j]) {
            common_elements[k++] = first[i];
            int cur = first[i];
            while (i < size_first && first[i] == cur) i++;
            while (j < size_second && second[j] == cur) j++;
        } else if (first[i] < second[j]) {
            i++;
        } else {
            j++;
        }
    }

    *res_size = count;
    return common_elements;
}

int main(void) {
    int arr1[] = {1, 8, 3, 2, 6};
    int arr2[] = {2, 6, 1};
    int size1 = sizeof(arr1)/sizeof(arr1[0]);
    int size2 = sizeof(arr2)/sizeof(arr2[0]);
    
    int res_size;
    int *intersection = f(arr1, arr2, size1, size2, &res_size); 
    
    // 用返回的res_size遍历，完全不会出现越界问题
    for(int i = 0; i < res_size; i++){
        printf("%d ", intersection[i]);
    }

    // 调用方手动释放堆内存，避免内存泄漏
    free(intersection);
    return 0;
}

内容的提问来源于stack exchange，提问作者kchemutai