2 a729276581 a729276581 于 2016.02.06 22:49 提问

leetcode Median of Two Sorted Arrays 1C

class Solution {

public:
double findMedianSortedArrays(vector& nums1, vector& nums2) {
if(nums1.size()==0){
if(nums2.size()%2==0)return ((double)nums2[nums2.size()/2]+nums2[nums2.size()/2-1])/2.0;
else return nums2[nums2.size()/2];
}
if(nums2.size()==0){
if(nums1.size()%2==0)return ((double)nums1[nums1.size()/2]+nums1[nums1.size()/2-1])/2.0;
else return nums1[nums1.size()/2];
}
int k=(nums1.size()+nums2.size())/2;
int m1=kth(0,nums1.size(),0,nums2.size(),nums1,nums2,k+1);
if(nums1.size()+nums2.size()==0){
int m2=kth(0,nums1.size(),0,nums2.size(),nums1,nums2,k);
return (m1+m2)/2.0;
}

return m1;
}
int kth(int a,int m ,int b,int n,vector& nums1, vector& nums2,int k){
if(n>m)return kth(b,n,a,m,nums2,nums1,k);
if(k==1)return min(nums1[a+0],nums2[b+0]);
if(n==0)return nums1[a+k-1];
int j=min(n,k/2);
int i=k-j;
if(nums1[a+i-1]>nums2[b+j-1])return kth(a,i,b+j,n-j,nums1,nums2,k-j);
return kth(a+i,m-i,b,j,nums1,nums2,k-i);
}
};

我输入的测例【1,1】 【1,1】的返回值是0
我想不通啊 就说返回错误也不可能取到比1小的数字 哪里来的零啊

2个回答

caozhy
caozhy   Ds   Rxr 2016.02.06 23:10
    if(k==1)return 
        min(nums1[a+0],nums2[b+0]);

    调试了下,这里b=2,越界了。
caozhy
caozhy 回复a729276581gs: C和C++本身都是很烂的语言。你用着70年代设计的编程语言。那时候的计算机对于系统资源来说是分毫必争。这正是C语言的哲学,不面向程序员,而面向机器。
接近 2 年之前 回复
a729276581
a729276581 我擦 c++ vector越界都不报错 好坑爹。。
接近 2 年之前 回复
caozhy
caozhy   Ds   Rxr 2016.02.06 23:13

代码不看了

http://blog.sina.com.cn/s/blog_62fc96e60101f8aa.html

这里的程序和你的思路完全一样,二分查找。你自己看下吧。

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!