C语言两有序数组求中位数代码的内存管理问题排查

本人具备Python中级水平，刚学习C语言，在LeetCode实现“寻找两个有序数组的中位数”题目时，采用插入排序思路编写了insert、merge、findMedianSortedArrays三个函数，但运行时触发AddressSanitizer的heap-use-after-free错误。虽尝试调整temp的内存分配方式，但问题仍未解决，现请求排查代码的内存管理问题并给出修复方案。

代码实现 #

int* insert(int* arr, int n, int x)
{
    int *ret = (int *) calloc(n+1,sizeof(int)), cont = 0;
    for(int i = 0; i<n && *(arr+i) < x; i++)
    {
        *(ret + i) = *(arr + i);
        cont++;
    }
    *(ret+cont) = x;
    for(int i = cont; i < n; i++)
    {
        *(ret+i+1) = *(arr + i);
    }
    return ret;
}
int* merge(int* arr1, int len1, int* arr2, int len2)
{
    int *ret = (int *) calloc(len1 + len2, sizeof(int)), **temp = (int **) malloc((len2+1)*sizeof(int *));
    for(int i = 0; i < len1; i++)
    {
        *(ret+i) = *(arr1+i);
    }
    *temp = ret;
    for(int i = 0; i < len2; i++)
    {
        *(temp+i+1) = insert(*(temp+i),len1+i, *(arr2+i));
    }
    for(int i = 0; i < len1+len2; i++)
    {
        *(ret + i) = *(*(temp+len2-1)+ i);
    }
    for(int i = 0; i < len2; i++)
    {
        free(*(temp+i));
    }
    free(temp);
    return ret;
}
double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size)
{
    int *arr = merge(nums1, nums1Size, nums2, nums2Size), len = nums1Size+ nums2Size;
    double mid;
    if(len % 2 == 1)
    {
        mid = *(arr + len/2);
    }
    else
    {
        mid = (*(arr+len/2)+*(arr+len/2+1))/2.0;
    }
    free(arr);
    return mid;
}

错误日志 #

=================================================================
==22==ERROR: AddressSanitizer: heap-use-after-free on address 0x602000000054 at pc 0x56200c01d257 bp 0x7fffc24d3340 sp 0x7fffc24d3330
READ of size 4 at 0x602000000054 thread T0
    #2 0x7f623c602082 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x24082)
0x602000000054 is located 4 bytes inside of 12-byte region [0x602000000050,0x60200000005c)
freed by thread T0 here:
    #0 0x7f623d010537 in __interceptor_free ../../../../src/libsanitizer/asan/asan_malloc_linux.cpp:127
    #4 0x7f623c602082 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x24082)
previously allocated by thread T0 here:
    #0 0x7f623d010a57 in __interceptor_calloc ../../../../src/libsanitizer/asan/asan_malloc_linux.cpp:154
    #4 0x7f623c602082 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x24082)
Shadow bytes around the buggy address:
  0x0c047fff7fb0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c047fff7fc0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c047fff7fd0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c047fff7fe0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c047fff7ff0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
=>0x0c047fff8000: fa fa 00 fa fa fa 04 fa fa fa[fd]fd fa fa fd fd
  0x0c047fff8010: fa fa 00 04 fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8020: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8030: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8040: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8050: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07 
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
  Shadow gap:              cc
==22==ABORTING

问题分析 #

1. 内存释放后非法访问：merge函数中，初始的ret指针被存入temp[0]，后续循环生成temp[1]到temp[len2]的插入结果数组。随后将temp[len2-1]的内容拷贝回ret，但执行free(*(temp+i))时，temp[0]就是ret的原始指针，导致ret被提前释放。最终返回ret后，在findMedianSortedArrays中访问已释放内存，触发heap-use-after-free错误。
2. 冗余内存操作：提前分配ret数组再用插入结果覆盖的操作完全多余，直接返回最后一次插入生成的数组即可。
3. 中位数计算错误：偶数长度数组的中位数应该取len/2-1和len/2位置的元素，原代码取len/2和len/2+1会导致下标越界或计算结果错误。

修复方案 #

int* insert(int* arr, int n, int x)
{
    int *ret = (int *) calloc(n+1, sizeof(int)), cont = 0;
    for(int i = 0; i < n && arr[i] < x; i++)
    {
        ret[i] = arr[i];
        cont++;
    }
    ret[cont] = x;
    for(int i = cont; i < n; i++)
    {
        ret[i+1] = arr[i];
    }
    return ret;
}

int* merge(int* arr1, int len1, int* arr2, int len2)
{
    int **temp = (int **) malloc((len2 + 1) * sizeof(int *));
    // 拷贝原数组到temp[0]，避免修改输入数组
    temp[0] = (int *) calloc(len1, sizeof(int));
    for(int i = 0; i < len1; i++)
    {
        temp[0][i] = arr1[i];
    }
    
    for(int i = 0; i < len2; i++)
    {
        temp[i+1] = insert(temp[i], len1 + i, arr2[i]);
        // 插入完成后立即释放上一次的数组，避免内存泄漏
        free(temp[i]);
    }
    
    int *result = temp[len2];
    free(temp);
    return result;
}

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size)
{
    int *arr = merge(nums1, nums1Size, nums2, nums2Size);
    int len = nums1Size + nums2Size;
    double mid;
    
    if(len % 2 == 1)
    {
        mid = arr[len/2];
    }
    else
    {
        mid = (arr[len/2 - 1] + arr[len/2]) / 2.0;
    }
    
    free(arr);
    return mid;
}

修复说明 #

• 去掉冗余的ret数组分配，直接返回最后一次插入生成的数组temp[len2]，避免内存重复操作。
• 每次插入完成后立即释放上一轮的数组，消除内存泄漏风险。
• 修正偶数长度数组的中位数计算逻辑，避免下标越界。
• 使用数组下标替代指针解引用，提升代码可读性。

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