g***j
发帖数: 1275 | 1 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);
}
}
}
}; | m*********a
发帖数: 3299 | 2 这个是最优解吗？
为啥不先merge 二个array m n
mediam=(m+n-1)/2 | R*****i
发帖数: 2126 | 3 最优解个P，代码可能最简洁，但call两个findkth()来求平均，实际中不会这么stupid
的。 | g***j
发帖数: 1275 | 4 那最优解是什么？
stupid
【在 R*****i 的大作中提到】
: 最优解个P，代码可能最简洁，但call两个findkth()来求平均，实际中不会这么stupid
: 的。
| R*****i
发帖数: 2126 | 5 感觉楼主走入了误区。Line1当然可以加等号，只不过后面的区间需要改写。记住一点
，确认那个k一定要在那个区间里，如果懒得去计较的话，每个半区间都扩加一个数的
话，用不用等号都没关系了。 | s*******y
发帖数: 12 | 6
上A
+2
这个题目真心比较tricky
【在 g***j 的大作中提到】
: 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:
| w*****d
发帖数: 105 | 7 leetcode上不是有原题吗？
最优解是O(logM + logN)。
google一下吧。 |
|
