主页 / coding / 问题 / 79196310
Accepted
golub001
Asked: 2024-11-17 08:24:01 +0800 CST

C 语言中 findMedianSortedArrays 函数的堆缓冲区溢出（LeetCode）

  • 772
double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {  
    int* asd;  
    bool flag1 = false, flag2 = false;  
    asd = malloc(sizeof(int) * (nums1Size + nums2Size));  
    int br1 = 0, br2 = 0;  

    for (int i = 0; i < (nums1Size + nums2Size); i++) {  
        if (flag1) {  
            asd[i] = nums2[br2];  
            br2++;  
        } else if (flag2) {  
            asd[i] = nums1[br1];  
            br1++;  
        } else if (nums1[br1] >= nums2[br2]) { 
            asd[i] = nums2[br2];  
            br2++;  
            if (br2 == nums2Size) {  
                br2--;  
                flag2 = true;  
            }  
        } else {  
            asd[i] = nums1[br1];  
            br1++;  
            if (br1 == nums1Size) {  
                br1--;  
                flag1 = true;  
            }  
        }  
        printf("%d\n", asd[i]);  
    }  

    if ((nums1Size + nums2Size) % 2 == 0) {  
        double a = (asd[(nums1Size + nums2Size) / 2] + asd[(nums1Size + nums2Size) / 2 - 1]);  
        return a / 2;  
    } else {  
        return asd[(nums1Size + nums2Size) / 2];  
    }  
}

测试用例很好，但无法提交。

当我尝试提交代码时，出现以下错误：

==23==错误：AddressSanitizer：地址 0x6020000001f0 上的堆缓冲区溢出
... 摘要：AddressSanitizer：findMedianSortedArrays 中的堆缓冲区溢出 solution.c:16
...

我怀疑问题是由于 br1 或 br2 超出了它们各自数组（nums1 或 nums2）的边界。我尝试为 br1 和 br2 添加边界检查，但仍然无法解决问题。我还验证了动态分配数组 asd 的大小（应该是 nums1Size + nums2Size），它似乎是正确的。合并数组或访问其元素的逻辑是否存在错误？我如何确保我不会访问 nums1 或 nums2 的越界内存？有没有更有效的方法来解决这个问题？

c

2 个回答

  1. 您根本没有检查是否存在其中一个数组为空的测试用例。如果其中一个数组为空，您提交的代码只会检查该空数组的第一个索引（因为您已将 br1 和 br2 初始化为 0）。以下是包含此案例的修复代码：

    double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
    int* asd;  
    bool flag1 = false, flag2 = false;  
    asd = malloc(sizeof(int) * (nums1Size + nums2Size));  
    int br1 = 0, br2 = 0;  
    if (nums2Size == 0){
        for(int i = 0;i<nums1Size;i++){
            asd[i] = nums1[i];
        }

    } else if (nums1Size == 0){
        for(int i = 0;i<nums2Size;i++){
            asd[i] = nums2[i];
        }
    }else {
        for (int i = 0; i < (nums1Size + nums2Size); i++) {  
            if (flag1) {  
                asd[i] = nums2[br2];  
                br2++;  
            } else if (flag2) {  
                asd[i] = nums1[br1];  
                br1++;  
            } else if (nums1[br1] >= nums2[br2]) {  //this is line 23 
                asd[i] = nums2[br2];  
                br2++;  
                if (br2 == nums2Size) {  
                    br2--;  
                    flag2 = true;  
                }  
            } else {  
                asd[i] = nums1[br1];  
                br1++;  
                if (br1 == nums1Size) {  
                    br1--;  
                    flag1 = true;  
                }  
            }  
            printf("%d\n", asd[i]);  
        }  
    }

    if ((nums1Size + nums2Size) % 2 == 0) {  
        double a = (asd[(nums1Size + nums2Size) / 2] + asd[(nums1Size + nums2Size) / 2 - 1]);  
        return a / 2;  
    } else {  
        return asd[(nums1Size + nums2Size) / 2];  
    }  
}

    您只需检查其中一个数组是否已为空。如果是，则返回非空列表，否则开始合并。提交代码并亲自查看。

    • 1
  2. Best Answer
    } else if (nums1[br1] >= nums2[br2]) {

    在此行中，如果数组为空，则您将访问超出范围的数组。

    由于返回前没有执行任何操作，因此您也泄漏了内存free(asd)。您甚至不需要进行任何分配即可找到中间元素。只需循环到中点并存储当前低值和上一个值（如果元素数量为偶数）。

    例子：

    #include <math.h>
#include <stddef.h>

double findMedianSortedArrays(int* nums1, size_t nums1Size, int* nums2,
                              size_t nums2Size) {
    size_t totSize = nums1Size + nums2Size;
    if (totSize == 0) return NAN; // not a number
    size_t mid = totSize / 2 + 1;
    int prev, curr = 0; // previous number and current number

    // Loop for as long as there are numbers left in both arrays
    // and we've not reached the midpoint
    for (; nums1Size && nums2Size && mid; --mid) {
        prev = curr; // store the previous number
        // store the smallest number in curr and step the
        // pointer in the selected array and decrease its size:
        if (*nums1 < *nums2) {
            curr = *nums1;
            ++nums1;
            --nums1Size;
        } else {
            curr = *nums2;
            ++nums2;
            --nums2Size;
        }
    }
    if (mid--) {
        // We haven't reach the midpoint so one of the arrays must have
        // more elements. Fast forward "mid" steps in that array:
        if (nums1Size) {
            nums1 += mid;
            if (mid) prev = nums1[-1];
            else prev = curr;
            curr = *nums1;
        } else {
            nums2 += mid;
            if (mid) prev = nums2[-1];
            else prev = curr;
            curr = *nums2;
        }
    }
    if (totSize % 2 == 0) return (prev + curr) / 2.0;
    return curr;
}

    演示

    • 0

相关问题