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一下吧。
相关阅读
有没有姐妹们做过IPL的弄个 的发型合适呢？请大家给点意见帮忙看一下，参加婚礼穿哪个比较合适急问，参加婚礼一定要穿西装打领带吗20包子求一个coach 25%off有人买过TBdress上的衣服吗coach 25% coupon古今中外最美的女人 (转载)nordstrom网上买的东西可以到店里退吗WSN可受教育 搞笑短片日剧 我的绅士时尚 03 如何选鞋 屌丝一秒变绅士男士皮鞋品牌推荐10个包子求coach正店coupon居然版主都没有了。。。谁知道这个牌子的包包在哪买 Cadice Toalj.crew买裤子质量有问题但是过了退换期还能退吗请问一下日版的松下NA95吹风机在美国用没问题吗？异常美丽的韩国女孩Jung Ryeo Won求推荐性价比高的指甲油想给妈妈买个包包，求个coach 正价店coupon为什么coach 下不了单