LeetCode#4寻找两个有序数组中位数Runtime Error问题求助

错误原因 #

出现addition of unsigned offset错误的核心原因是vector索引越界，结合代码细节，具体问题如下：

• 空数组提前调用findMedian导致越界：当其中一个数组为空时（比如nums1.size()=0），findMedianSortedArrays中传入的e1 = (int)nums1.size()-1 = -1，进入divConq后会先执行double med1 = findMedian(nums1, s1, e1)，此时findMedian里计算middle=(0 + (-1))/2 = -1，访问nums[middle]即nums[-1]，直接触发越界。
• 逻辑判断错误导致索引越界：在len2 == 1的分支中，错误地将med2和索引值windowIndexHigh/windowIndexLow比较，而非对应位置的数组元素nums1[windowIndexHigh]/nums1[windowIndexLow]，逻辑错误会导致递归时传入非法的起止索引，进而越界；另外前面已经将nums1设为较长的数组（len1 >= len2），但后续仍保留if(len1 <= len2)的判断分支，这些分支永远不会被执行，导致递归逻辑缺失，最终触发异常。
• 固定索引访问切片数组导致越界：在len2 == 2 && len1 == 2的base case中，直接使用nums1[0]、nums1[1]访问，但此时nums1的有效范围是s1到e1（并非从0开始），固定索引会导致越界。

修复方案 #

针对上述问题，逐一修正：

• 调整空数组判断顺序：在调用findMedian前先判断数组是否为空，避免对空数组执行索引访问。
• 修正比较逻辑：将med2与索引对应的数组元素比较，而非索引本身。
• 移除无效分支：删除if(len1 <= len2)的判断分支，因为前面已经保证nums1是较长数组，len1 >= len2恒成立。
• 修正切片数组的索引访问：在base case中使用s1、e1等动态索引访问数组元素，而非固定的0、1。
• 补充分支的返回逻辑：在len2 ==1的分支中，所有条件分支都要有明确返回值，避免执行到分支外的代码。

修正后的代码 #

#include <bits/stdc++.h>
using namespace std;

class Solution {
double findMedian(vector<int> &nums, int begin, int end){
    int middle = (begin + end)/2;
    return (end - begin + 1) %2 == 0 ? \
    ((double)nums[middle] + (double)nums[middle+1])/2.0 \
    : nums[middle];
}

double divConq(vector<int>& input1, vector<int>& input2, int s1, int e1, int s2, int e2){
    int len1 = e1 - s1 + 1;
    int len2 = e2 - s2 + 1;

    // nums1 always longer
    vector<int>& nums1 = len1 >= len2 ? input1 : input2;
    vector<int>& nums2 = len1 >= len2 ? input2 : input1;
    int s_long = len1 >= len2 ? s1 : s2;
    int e_long = len1 >= len2 ? e1 : e2;
    int s_short = len1 >= len2 ? s2 : s1;
    int e_short = len1 >= len2 ? e2 : e1;
    len1 = e_long - s_long + 1;
    len2 = e_short - s_short + 1;

    // 先处理空数组情况，避免调用findMedian越界
    if(len1 == 0){
        return len2 ==0 ? 0.0 : findMedian(nums2, s_short, e_short);
    }
    if(len2 == 0){
        return findMedian(nums1, s_long, e_long);
    }

    double med1 = findMedian(nums1, s_long, e_long);
    double med2 = findMedian(nums2, s_short, e_short);

    // base case with list of length 1
    if(len1 == 1 && len2 == 1){
        return (med1 + med2)/2.0;
    }
    if(len2 == 1){
        int windowIndexLow = len1 %2 ==0 ? ((s_long + e_long)/2)-1 : ((s_long + e_long)/2);
        int windowIndexHigh = len1 %2 ==0 ? windowIndexLow +2 : windowIndexLow +1;

        if(len1 %2 ==0){
            if(med2 >= nums1[windowIndexLow] && med2 <= nums1[windowIndexHigh]){
                return ((double)(med2 + med1))/2.0;
            } else if(med2 > nums1[windowIndexHigh]){
                return findMedian(nums1, s_long+1, e_long);
            } else if(med2 < nums1[windowIndexLow]){
                return findMedian(nums1, s_long, e_long-1);
            }
        } else {
            if(med2 >= nums1[windowIndexLow] && med2 <= nums1[windowIndexHigh]){
                return med2;
            } else if(med2 > nums1[windowIndexHigh]){
                return findMedian(nums1, s_long+1, e_long);
            } else if(med2 < nums1[windowIndexLow]){
                return findMedian(nums1, s_long, e_long-1);
            }
        }
        return -1.0; // 兜底返回，避免编译警告
    }

    // base case with lists of length 2
    if(len2 ==2 && len1 ==2){
        return (max(nums1[s_long], nums2[s_short]) + min(nums1[e_long], nums2[e_short]))/2.0;
    }

    // 仅保留len1 >= len2的分支，因为前面已经保证nums1是较长数组
    int cut = len2/2;
    // case 1.3: delete top half of nums2 and some of nums1
    if(med2 >= med1){
        return divConq(nums1, nums2, s_long + cut, e_long, s_short, e_short - cut);
    }
    // case 1.4: delete bottom half of nums2 and some of nums1
    if(med2 <= med1){
        return divConq(nums1, nums2, s_long, e_long - cut, s_short + cut, e_short);
    }

    return -1.0;
}

public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int e1 = nums1.empty() ? -1 : (int)nums1.size()-1;
        int e2 = nums2.empty() ? -1 : (int)nums2.size()-1;
        return divConq(nums1, nums2, 0, e1, 0, e2);
    }
};

额外说明 #

修正后的代码解决了索引越界问题，同时优化了数组长短判断后的变量传递逻辑，避免原代码中swap(s1,s2)可能带来的混淆。递归逻辑也更清晰，符合分治算法的核心思路。

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