我写了下面的代码来找到两个排序数组的中位数并且它在本地运行良好,但是当我提交到 leetcode 时我得到运行时错误:添加无符号偏移量(stl_vector.h)
这是代码:
#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;
//cout << "length len1: " << len1 << " length len2: " << len2 << '\n';
//nums1 always longer
vector<int>& nums1 = len1 >= len2 ? input1 : input2;
vector<int>& nums2 = len1 >= len2 ? input2 : input1;
if (nums1 != input1){swap(s1, s2); swap(e1, e2);}
double med1 = findMedian(nums1, s1, e1);
double med2 = findMedian(nums2, s2, e2);
//trivial cases
if(len1 == 0){return med2;}
if(len2 == 0){return med1;}
//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? ((s1+e1)/2)-1 : ((s1+e1)/2);
int windowIndexHigh = len1 % 2 == 0? windowIndexLow + 2 : windowIndexLow + 1;
//cout << "length of nums2 is 1" << '\n';
if(len1 % 2 == 0){
if(med2 >= nums1[windowIndexLow] && med2 <= nums1[windowIndexHigh]){
return ((double)(med2 + med1)) / 2.0;
}
else if(med2 > windowIndexHigh){
return findMedian(nums1, s1+1, e1);
}
else if(med2 < windowIndexLow){
return findMedian(nums1, s1, e1-1);
}
}
else{
if(med2 >= nums1[windowIndexLow] && med2 <= nums1[windowIndexHigh]){
return med2;
}
else if(med2 > windowIndexHigh){
return findMedian(nums1, s1+1, e1);
}
else if(med2 < windowIndexLow){
return findMedian(nums1, s1, e1-1);
}
return -1.0;
}
}
//base case with lists of length 2
if(len2 == 2 && len1 == 2){
return (max(nums1[0], nums2[0]) + \
min(nums1[1], nums2[1]))/2.0;
}
//case 1.1: delete top half of nums1 and some of nums2
if(len1 <= len2 && med1 >= med2){
int cut = (len1)/2;
return divConq(nums1, nums2, s1, e1-cut, s2+cut, e2);
}
//case 1.2: delete bottom half of nums1 and some of nums2
if(len1 <= len2 && med1 <= med2){
int cut = (len1)/2;
return divConq(nums1, nums2, s1+cut, e1, s2, e2-cut);
}
//case 1.3: delete top half of nums2 and some of nums1
if(len1 >= len2 && med2 >= med1){
int cut = (len2)/2;
return divConq(nums1, nums2, s1+cut, e1, s2, e2-cut);
}
//case 1.4: delete bottom half of nums2 and some of nums1
if(len1 >= len2 && med2 <= med1){
int cut = (len2)/2;
return divConq(nums1, nums2, s1, e1-cut, s2+cut, e2);
}
return -1.0;
}
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
return divConq(nums1, nums2, 0, (int)nums1.size() - 1, 0, (int)nums2.size() - 1);
}
};
有谁知道为什么会这样,我能做些什么来解决这个问题?
我在本地运行我的代码,在 g++ 编译器上逐字逐句地运行,它适用于每个测试用例。我在网上搜索过这个问题,没有看到任何类似的投诉得到满意的答复。我检查了官方解决方案,但我的解决方案看起来更整洁、更清晰,而且在我看来我尊重矢量结构。有人可以帮我解决这个问题吗?
您的错误可能与您所说的琐碎案例有关。给定一个零长度数组,
findMedian
函数会导致数组越界异常。
也许你可以通过将简单的案例检查与对
findMedian
的调用交换来修复错误,即
//trivial cases
if(len1 == 0){return -1.0;}
if(len2 == 0){return -1.0;}
double med1 = findMedian(nums1, s1, e1);
double med2 = findMedian(nums2, s2, e2);
虽然我对这个问题的了解还不够,无法知道
-1.0
的虚拟返回值是否正确。