g*j
2 楼
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);
}
}
}
};
这个题目，有两个地方总是想不明白
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);
}
}
}
};
d*x
3 楼
不管老系统egov.uscis.gov还是新系统myaccount.uscis.gov，都没有更新信息。只能
在老系统里看到last updated: 11/29/2018，但内容还是10/23 scheduled interview
。请问这是怎么回事？
在老系统里看到last updated: 11/29/2018，但内容还是10/23 scheduled interview
。请问这是怎么回事？
b*s
4 楼
想买cream的赶紧啦
c*u
5 楼
co ask
【在 t********f 的大作中提到】
: 请教一下，像OMEGA这一类的手表哪里能买到便宜一点的？国内的朋友想让帮忙买一块
: 。谢谢大家了。
【在 t********f 的大作中提到】
: 请教一下，像OMEGA这一类的手表哪里能买到便宜一点的？国内的朋友想让帮忙买一块
: 。谢谢大家了。
m*a
6 楼
这个是最优解吗？
为啥不先merge 二个array m n
mediam=(m+n-1)/2
为啥不先merge 二个array m n
mediam=(m+n-1)/2
V*s
7 楼
我是看见了 反而状态倒退了
R*i
8 楼
最优解个P，代码可能最简洁，但call两个findkth()来求平均，实际中不会这么stupid
的。
的。
g*j
9 楼
那最优解是什么？
stupid
【在 R*****i 的大作中提到】
: 最优解个P，代码可能最简洁，但call两个findkth()来求平均，实际中不会这么stupid
: 的。
stupid
【在 R*****i 的大作中提到】
: 最优解个P，代码可能最简洁，但call两个findkth()来求平均，实际中不会这么stupid
: 的。
R*i
10 楼
感觉楼主走入了误区。Line1当然可以加等号，只不过后面的区间需要改写。记住一点
，确认那个k一定要在那个区间里，如果懒得去计较的话，每个半区间都扩加一个数的
话，用不用等号都没关系了。
，确认那个k一定要在那个区间里，如果懒得去计较的话，每个半区间都扩加一个数的
话，用不用等号都没关系了。
s*y
11 楼
上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
12 楼
leetcode上不是有原题吗？
最优解是O(logM + logN)。
google一下吧。
最优解是O(logM + logN)。
google一下吧。
相关阅读
请教个问题，DHC 卸妆油除了他家官网，哪里能买到？倩碧官网deal:6个小样+一个包包这几天的，加shopping战果巩俐为什么总是一副合不拢嘴的大妈表情挣包子，红裙子请教Borghese的绿泥 红泥MMs 在美国都吃什么保健品？LANCOME good deal请教姐妹们，最近老公身上开始出现尸斑，有什么办法？小个子女生哪里买泳装和游泳衣选择多？白色皮包上的圆珠笔印怎么去grape seed extract有什么美容效果今天去动物园放了个风～（闪完睡觉了）红酒咖啡与狼共舞 QQ群开通theory的blouse昨天看到3个拉拉(在上海) (转载)（参加活动）我唯一的红裙看上一个眼花缭乱的包包crossbody包包选择配个什么包呢？