百思不得其解的一道题目

发信人: gmadj (干嘛爱打架), 信区: JobHunting
标  题: 百思不得其解的一道题目
发信站: BBS 未名空间站 (Wed Jul 30 20:59:42 2014, 美东)


Median of Two Sorted Arrays

这个题目，有两个地方总是想不明白
1) Line 1，这个地方为啥不能加等号，加了就会出错，为啥else部分可以处理这个等
号的情况呢？
2) Line 2 and Line 3，这两个地方为啥是 m/2 + n/2 +1 >=k，我理解的是如果算上A
[m/2] B[/2] 总共有m/2+n/2 +2 个元素，那么就是说 m/2 + n/2 +2 > k， 分别换成
这句话，这里是work的，但是我的疑问是，为啥加一个等号就不work了，m/2 + n/2 +2
>= k，为啥在else部分，就可以处理这个等号的情况呢？



class Solution {
public:
    double findMedianSortedArrays(int A[], int m, int B[], int n) {
       
        if((n + m) % 2 == 0) {
            return (findkth(A, m, B, n, (m+n)/2) + findkth(A, m, B, n, (m+n)
/2 + 1))*0.5;
        } else {
            return findkth(A, m, B, n, (m+n)/2 + 1);
        }
       
    }
   
    double findkth(int A[], int m, int B[], int n, int k) {  
       
        if(m == 0) return B[k-1];
       
        if(n == 0) return A[k-1];

        if(k == 1) return min(A[0], B[0]);  
       
        if(A[m/2] > B[n/2]) {                              // Line 1
            if(m/2 + n/2 + 1 >= k ) {                  // Line 2
               return findkth(A, m/2 , B, n, k); 
            } else {
               return findkth(A, m, B + n/2 + 1, n - n/2 - 1, k - n/2 -1);
            }  
        } else {
            if(m/2 + n/2 + 1 >= k ) {                  //Line 3
                return findkth(A, m, B, n/2, k);  
            } else {
                return findkth(A + m/2 + 1, m - m/2 - 1, B, n, k - m/2 - 1);
            }
        }   
    }
};
--
※ 来源:·WWW 未名空间站 网址：mitbbs.com 移动：在应用商店搜索未名空间·[FROM: 64.]

http://www.mitbbs.com/article_t/JobHunting/32747485.html

FT中文十大 华尔街中文十大 水木十大 小百合十大 饮水思源十大 日月光华十大

京东暑期阅读大放价，少儿图书满200立减100 ， 更多京东优惠券