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的赶紧啦
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
的。
的。
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一下吧。
相关阅读
女大十八变,变来变去进医院败家才有时尚,花钱才有漂亮这是一个看脸的时代为什么觉得孕妇照都丑爆了跟潮流剪了短发,才发现短发也太难打理了吧[美容美体]化妆开运(转载)男友嫌她胖,她抽脂做肥皂送男友哪里买有push-up的泳衣?这个被机器人攻占了吗?实力搬运,脱发的那些事(转载)揭秘怎样洗头不伤发国内超模秀和国外超模秀的差皮肤晒黑怎样美白 10个绝招快速白回来(转载)干到掉皮!请推荐超级滋润的粉底液舍友不讲卫生,头发长了虱子竟然还不愿洗头那些不承认自己整容的女明星kiehl's的$20rewards cash 是不是不能在local店里用啊?不想再为国家省布料了,求长高!面相对自己的毒害你更喜欢和谁逛街,男票还是闺蜜?