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

Question

    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]) {  //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];  
    }  
}  

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

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

==23==错误：AddressSanitizer：地址 0x6020000001f0 上堆缓冲区溢出
... 摘要：AddressSanitizer：堆缓冲区溢出解决方案.c:16 in findMedianSortedArrays
...

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

Answer 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];  
    }  
}

You simply check if one of arrays was already empty. If so, you return the non-empty list, otherwise you start merging.