支持于洋这组运动员的，请到ESPN网上投票，正在进行 (转载)# Joke - 肚皮舞运动
S*g
1 楼
至少以前是 现在不知道
Kth/median of 2 sorted array...
leetcode上程序非常繁琐
大家有没有好的解法？
thanks
Kth/median of 2 sorted array...
leetcode上程序非常繁琐
大家有没有好的解法？
thanks
r*c
2 楼
车里温度表已经30度了
h*s
3 楼
【 以下文字转载自 Olympics 讨论区 】
发信人: zaosen (leng), 信区: Olympics
标 题: 支持于洋这组运动员的，请到ESPN网上投票，正在进行 (转载)
发信站: BBS 未名空间站 (Thu Aug 2 16:33:22 2012, 美东)
发信人: ourname (ourname), 信区: Badminton
标 题: 支持于洋这组运动员的，请到ESPN网上投票，正在进行
发信站: BBS 未名空间站 (Thu Aug 2 15:03:23 2012, 美东)
http://espn.go.com/olympics/
发信人: zaosen (leng), 信区: Olympics
标 题: 支持于洋这组运动员的，请到ESPN网上投票，正在进行 (转载)
发信站: BBS 未名空间站 (Thu Aug 2 16:33:22 2012, 美东)
发信人: ourname (ourname), 信区: Badminton
标 题: 支持于洋这组运动员的，请到ESPN网上投票，正在进行
发信站: BBS 未名空间站 (Thu Aug 2 15:03:23 2012, 美东)
http://espn.go.com/olympics/
S*g
4 楼
saw this online
http://haixiaoyang.wordpress.com/2012/06/19/kth-element-in-2-so
but i dont understand why a and b are switched position in the second else
block...
http://haixiaoyang.wordpress.com/2012/06/19/kth-element-in-2-so
but i dont understand why a and b are switched position in the second else
block...
Y*r
5 楼
你什么车可以显示摄氏度？
【在 r*c 的大作中提到】
: 车里温度表已经30度了
【在 r*c 的大作中提到】
: 车里温度表已经30度了
x*g
6 楼
Not a fair question.
I have problem with the end result.
But it wasn't the player's fault.
So I don't have a problem with the teams....
【在 h***s 的大作中提到】
: 【 以下文字转载自 Olympics 讨论区 】
: 发信人: zaosen (leng), 信区: Olympics
: 标 题: 支持于洋这组运动员的，请到ESPN网上投票，正在进行 (转载)
: 发信站: BBS 未名空间站 (Thu Aug 2 16:33:22 2012, 美东)
: 发信人: ourname (ourname), 信区: Badminton
: 标 题: 支持于洋这组运动员的，请到ESPN网上投票，正在进行
: 发信站: BBS 未名空间站 (Thu Aug 2 15:03:23 2012, 美东)
: http://espn.go.com/olympics/
I have problem with the end result.
But it wasn't the player's fault.
So I don't have a problem with the teams....
【在 h***s 的大作中提到】
: 【 以下文字转载自 Olympics 讨论区 】
: 发信人: zaosen (leng), 信区: Olympics
: 标 题: 支持于洋这组运动员的，请到ESPN网上投票，正在进行 (转载)
: 发信站: BBS 未名空间站 (Thu Aug 2 16:33:22 2012, 美东)
: 发信人: ourname (ourname), 信区: Badminton
: 标 题: 支持于洋这组运动员的，请到ESPN网上投票，正在进行
: 发信站: BBS 未名空间站 (Thu Aug 2 15:03:23 2012, 美东)
: http://espn.go.com/olympics/
r*m
7 楼
黄蓉gg的啊。。。没仔细看啊，应该可以再优化一些吧。
a,b每次应该都能减半的 O(logK)
【在 S********g 的大作中提到】
: saw this online
: http://haixiaoyang.wordpress.com/2012/06/19/kth-element-in-2-so
: but i dont understand why a and b are switched position in the second else
: block...
r*c
8 楼
车里当然显示86F,人工换算的
K*m
9 楼
目前我能想到最好的建最小堆 (lgm+lgn)
当然了，建堆也需要时间的
【在 S********g 的大作中提到】
: 至少以前是 现在不知道
: Kth/median of 2 sorted array...
: leetcode上程序非常繁琐
: 大家有没有好的解法？
: thanks
当然了，建堆也需要时间的
【在 S********g 的大作中提到】
: 至少以前是 现在不知道
: Kth/median of 2 sorted array...
: leetcode上程序非常繁琐
: 大家有没有好的解法？
: thanks
w*x
10 楼
我这个id和黄蓉有半毛钱的关系吗 -_- , 彩虹mm?
【在 r*******m 的大作中提到】
:
: 黄蓉gg的啊。。。没仔细看啊，应该可以再优化一些吧。
: a,b每次应该都能减半的 O(logK)
t*e
11 楼
觉得leetcode上的解挺intuitive的 也不复杂啊 二分法的idea
p*2
12 楼
这题Java写很不好写。
S*g
13 楼
是啊 二爷一语中的。。
C里面可以array A＋i 好象java里面不行。。。
面试的时候可不可以 就这一道题用C写啊。。。。
C里面可以array A＋i 好象java里面不行。。。
面试的时候可不可以 就这一道题用C写啊。。。。
l*a
14 楼
你为什么这道会用C,别的题就不会用C ne
【在 S********g 的大作中提到】
: 是啊 二爷一语中的。。
: C里面可以array A＋i 好象java里面不行。。。
: 面试的时候可不可以 就这一道题用C写啊。。。。
【在 S********g 的大作中提到】
: 是啊 二爷一语中的。。
: C里面可以array A＋i 好象java里面不行。。。
: 面试的时候可不可以 就这一道题用C写啊。。。。
g*e
15 楼
把首尾两个index都传进去就可以了
search(int[] a, int startA, int endA, int[] b, int startB, int endB)
【在 S********g 的大作中提到】
: 是啊 二爷一语中的。。
: C里面可以array A＋i 好象java里面不行。。。
: 面试的时候可不可以 就这一道题用C写啊。。。。
search(int[] a, int startA, int endA, int[] b, int startB, int endB)
【在 S********g 的大作中提到】
: 是啊 二爷一语中的。。
: C里面可以array A＋i 好象java里面不行。。。
: 面试的时候可不可以 就这一道题用C写啊。。。。
p*2
16 楼
这道题我碰到过。在提示下给了一个思路，最后拿到offer了。面试的时候不一定要求
那么高。
这题如果没做过的话基本是做不出来。我以前在leetcode上扫了一眼，觉得面试不会出
这么变态的题。面试之前在glassdoor上看到这个公司出了几次这题，也没提起注意，
没想到还真给碰到了。
【在 S********g 的大作中提到】
: 是啊 二爷一语中的。。
: C里面可以array A＋i 好象java里面不行。。。
: 面试的时候可不可以 就这一道题用C写啊。。。。
p*2
17 楼
以前写过，不好写。你有过了OJ的code吗？
【在 g*****e 的大作中提到】
: 把首尾两个index都传进去就可以了
: search(int[] a, int startA, int endA, int[] b, int startB, int endB)
w*x
18 楼
二爷威武啊~~~~
【在 p*****2 的大作中提到】
:
: 以前写过，不好写。你有过了OJ的code吗？
p*2
19 楼
你是不是已经拿到了，怎么看不到你做题了。
【在 w****x 的大作中提到】
:
: 二爷威武啊~~~~
c*t
20 楼
也可以传search(int[] a, int index1, int[] b, int index2, int k), 用recursion
, 代码也就 10来行。
可是如果没有做过，即使知道二分法，也真的很难一次写对
【在 g*****e 的大作中提到】
: 把首尾两个index都传进去就可以了
: search(int[] a, int startA, int endA, int[] b, int startB, int endB)
, 代码也就 10来行。
可是如果没有做过，即使知道二分法，也真的很难一次写对
【在 g*****e 的大作中提到】
: 把首尾两个index都传进去就可以了
: search(int[] a, int startA, int endA, int[] b, int startB, int endB)
w*o
21 楼
这是我见过的最精简的算法，可以用java实现。复杂度是O（lg（m））比leetcode上的
还快。leetcode上的几个实现基本都是merge或merge＋binary search的思想，这个是
纯binary search，核心部分只有十几行：（过了OJ）
public double findMedianSortedArrays(int A[], int B[]) {
if((A == null ||A.length == 0) && (B == null || B.length == 0))
return 0.0;
if (A.length >= B.length)
return findMedianSortedArraysInternal(B, A);
else
return findMedianSortedArraysInternal(A, B);
}
double findMedianSortedArraysInternal(int[] A, int[] B) {
int m = A.length;
int n = B.length;
int k = (n + m - 1) / 2;
int l = 0, r = m; // this is m not m-1
while (l < r) {
int mid = l + (r - l) / 2, bIdx = k - mid;
if (bIdx > k || A[mid] < B[bIdx]) {
l = mid + 1;
} else {
r = mid;
}
}
int a = l - 1 >= 0? A[l - 1] : Integer.MIN_VALUE;
int b = k - l >= 0? B[k - l] : Integer.MIN_VALUE;
a = a >= b ? a : b;
if( (n + m) % 2 == 1)
return a;
int c = k - l + 1 >= n? Integer.MAX_VALUE: B[k - l + 1];
int d = l >= m? Integer.MAX_VALUE: A[l];
c = c <= d ? c : d;
return ((double) (a + c)) / 2.0;
}
还快。leetcode上的几个实现基本都是merge或merge＋binary search的思想，这个是
纯binary search，核心部分只有十几行：（过了OJ）
public double findMedianSortedArrays(int A[], int B[]) {
if((A == null ||A.length == 0) && (B == null || B.length == 0))
return 0.0;
if (A.length >= B.length)
return findMedianSortedArraysInternal(B, A);
else
return findMedianSortedArraysInternal(A, B);
}
double findMedianSortedArraysInternal(int[] A, int[] B) {
int m = A.length;
int n = B.length;
int k = (n + m - 1) / 2;
int l = 0, r = m; // this is m not m-1
while (l < r) {
int mid = l + (r - l) / 2, bIdx = k - mid;
if (bIdx > k || A[mid] < B[bIdx]) {
l = mid + 1;
} else {
r = mid;
}
}
int a = l - 1 >= 0? A[l - 1] : Integer.MIN_VALUE;
int b = k - l >= 0? B[k - l] : Integer.MIN_VALUE;
a = a >= b ? a : b;
if( (n + m) % 2 == 1)
return a;
int c = k - l + 1 >= n? Integer.MAX_VALUE: B[k - l + 1];
int d = l >= m? Integer.MAX_VALUE: A[l];
c = c <= d ? c : d;
return ((double) (a + c)) / 2.0;
}
g*e
22 楼
我刚被storm8还是quantcast问了。。。
【在 S********g 的大作中提到】
: 至少以前是 现在不知道
: Kth/median of 2 sorted array...
: leetcode上程序非常繁琐
: 大家有没有好的解法？
: thanks
【在 S********g 的大作中提到】
: 至少以前是 现在不知道
: Kth/median of 2 sorted array...
: leetcode上程序非常繁琐
: 大家有没有好的解法？
: thanks
S*g
23 楼
至少以前是 现在不知道
Kth/median of 2 sorted array...
leetcode上程序非常繁琐
大家有没有好的解法？
thanks
Kth/median of 2 sorted array...
leetcode上程序非常繁琐
大家有没有好的解法？
thanks
S*g
24 楼
saw this online
http://haixiaoyang.wordpress.com/2012/06/19/kth-element-in-2-so
but i dont understand why a and b are switched position in the second else
block...
http://haixiaoyang.wordpress.com/2012/06/19/kth-element-in-2-so
but i dont understand why a and b are switched position in the second else
block...
r*m
25 楼
黄蓉gg的啊。。。没仔细看啊，应该可以再优化一些吧。
a,b每次应该都能减半的 O(logK)
【在 S********g 的大作中提到】
: saw this online
: http://haixiaoyang.wordpress.com/2012/06/19/kth-element-in-2-so
: but i dont understand why a and b are switched position in the second else
: block...
K*m
26 楼
目前我能想到最好的建最小堆 (lgm+lgn)
当然了，建堆也需要时间的
【在 S********g 的大作中提到】
: 至少以前是 现在不知道
: Kth/median of 2 sorted array...
: leetcode上程序非常繁琐
: 大家有没有好的解法？
: thanks
当然了，建堆也需要时间的
【在 S********g 的大作中提到】
: 至少以前是 现在不知道
: Kth/median of 2 sorted array...
: leetcode上程序非常繁琐
: 大家有没有好的解法？
: thanks
w*x
27 楼
我这个id和黄蓉有半毛钱的关系吗 -_- , 彩虹mm?
【在 r*******m 的大作中提到】
:
: 黄蓉gg的啊。。。没仔细看啊，应该可以再优化一些吧。
: a,b每次应该都能减半的 O(logK)
t*e
28 楼
觉得leetcode上的解挺intuitive的 也不复杂啊 二分法的idea
p*2
29 楼
这题Java写很不好写。
S*g
30 楼
是啊 二爷一语中的。。
C里面可以array A＋i 好象java里面不行。。。
面试的时候可不可以 就这一道题用C写啊。。。。
C里面可以array A＋i 好象java里面不行。。。
面试的时候可不可以 就这一道题用C写啊。。。。
l*a
31 楼
你为什么这道会用C,别的题就不会用C ne
【在 S********g 的大作中提到】
: 是啊 二爷一语中的。。
: C里面可以array A＋i 好象java里面不行。。。
: 面试的时候可不可以 就这一道题用C写啊。。。。
【在 S********g 的大作中提到】
: 是啊 二爷一语中的。。
: C里面可以array A＋i 好象java里面不行。。。
: 面试的时候可不可以 就这一道题用C写啊。。。。
g*e
32 楼
把首尾两个index都传进去就可以了
search(int[] a, int startA, int endA, int[] b, int startB, int endB)
【在 S********g 的大作中提到】
: 是啊 二爷一语中的。。
: C里面可以array A＋i 好象java里面不行。。。
: 面试的时候可不可以 就这一道题用C写啊。。。。
search(int[] a, int startA, int endA, int[] b, int startB, int endB)
【在 S********g 的大作中提到】
: 是啊 二爷一语中的。。
: C里面可以array A＋i 好象java里面不行。。。
: 面试的时候可不可以 就这一道题用C写啊。。。。
p*2
33 楼
这道题我碰到过。在提示下给了一个思路，最后拿到offer了。面试的时候不一定要求
那么高。
这题如果没做过的话基本是做不出来。我以前在leetcode上扫了一眼，觉得面试不会出
这么变态的题。面试之前在glassdoor上看到这个公司出了几次这题，也没提起注意，
没想到还真给碰到了。
【在 S********g 的大作中提到】
: 是啊 二爷一语中的。。
: C里面可以array A＋i 好象java里面不行。。。
: 面试的时候可不可以 就这一道题用C写啊。。。。
p*2
34 楼
以前写过，不好写。你有过了OJ的code吗？
【在 g*****e 的大作中提到】
: 把首尾两个index都传进去就可以了
: search(int[] a, int startA, int endA, int[] b, int startB, int endB)
w*x
35 楼
二爷威武啊~~~~
【在 p*****2 的大作中提到】
:
: 以前写过，不好写。你有过了OJ的code吗？
p*2
36 楼
你是不是已经拿到了，怎么看不到你做题了。
【在 w****x 的大作中提到】
:
: 二爷威武啊~~~~
c*t
37 楼
也可以传search(int[] a, int index1, int[] b, int index2, int k), 用recursion
, 代码也就 10来行。
可是如果没有做过，即使知道二分法，也真的很难一次写对
【在 g*****e 的大作中提到】
: 把首尾两个index都传进去就可以了
: search(int[] a, int startA, int endA, int[] b, int startB, int endB)
, 代码也就 10来行。
可是如果没有做过，即使知道二分法，也真的很难一次写对
【在 g*****e 的大作中提到】
: 把首尾两个index都传进去就可以了
: search(int[] a, int startA, int endA, int[] b, int startB, int endB)
w*o
38 楼
这是我见过的最精简的算法，可以用java实现。复杂度是O（lg（m））比leetcode上的
还快。leetcode上的几个实现基本都是merge或merge＋binary search的思想，这个是
纯binary search，核心部分只有十几行：（过了OJ）
public double findMedianSortedArrays(int A[], int B[]) {
if((A == null ||A.length == 0) && (B == null || B.length == 0))
return 0.0;
if (A.length >= B.length)
return findMedianSortedArraysInternal(B, A);
else
return findMedianSortedArraysInternal(A, B);
}
double findMedianSortedArraysInternal(int[] A, int[] B) {
int m = A.length;
int n = B.length;
int k = (n + m - 1) / 2;
int l = 0, r = m; // this is m not m-1
while (l < r) {
int mid = l + (r - l) / 2, bIdx = k - mid;
if (bIdx > k || A[mid] < B[bIdx]) {
l = mid + 1;
} else {
r = mid;
}
}
int a = l - 1 >= 0? A[l - 1] : Integer.MIN_VALUE;
int b = k - l >= 0? B[k - l] : Integer.MIN_VALUE;
a = a >= b ? a : b;
if( (n + m) % 2 == 1)
return a;
int c = k - l + 1 >= n? Integer.MAX_VALUE: B[k - l + 1];
int d = l >= m? Integer.MAX_VALUE: A[l];
c = c <= d ? c : d;
return ((double) (a + c)) / 2.0;
}
还快。leetcode上的几个实现基本都是merge或merge＋binary search的思想，这个是
纯binary search，核心部分只有十几行：（过了OJ）
public double findMedianSortedArrays(int A[], int B[]) {
if((A == null ||A.length == 0) && (B == null || B.length == 0))
return 0.0;
if (A.length >= B.length)
return findMedianSortedArraysInternal(B, A);
else
return findMedianSortedArraysInternal(A, B);
}
double findMedianSortedArraysInternal(int[] A, int[] B) {
int m = A.length;
int n = B.length;
int k = (n + m - 1) / 2;
int l = 0, r = m; // this is m not m-1
while (l < r) {
int mid = l + (r - l) / 2, bIdx = k - mid;
if (bIdx > k || A[mid] < B[bIdx]) {
l = mid + 1;
} else {
r = mid;
}
}
int a = l - 1 >= 0? A[l - 1] : Integer.MIN_VALUE;
int b = k - l >= 0? B[k - l] : Integer.MIN_VALUE;
a = a >= b ? a : b;
if( (n + m) % 2 == 1)
return a;
int c = k - l + 1 >= n? Integer.MAX_VALUE: B[k - l + 1];
int d = l >= m? Integer.MAX_VALUE: A[l];
c = c <= d ? c : d;
return ((double) (a + c)) / 2.0;
}
g*e
39 楼
我刚被storm8还是quantcast问了。。。
【在 S********g 的大作中提到】
: 至少以前是 现在不知道
: Kth/median of 2 sorted array...
: leetcode上程序非常繁琐
: 大家有没有好的解法？
: thanks
【在 S********g 的大作中提到】
: 至少以前是 现在不知道
: Kth/median of 2 sorted array...
: leetcode上程序非常繁琐
: 大家有没有好的解法？
: thanks
l*b
40 楼
mark一下
m*d
41 楼
ft，我这次onsite也被问到了这题
【在 S********g 的大作中提到】
: 至少以前是 现在不知道
: Kth/median of 2 sorted array...
: leetcode上程序非常繁琐
: 大家有没有好的解法？
: thanks
【在 S********g 的大作中提到】
: 至少以前是 现在不知道
: Kth/median of 2 sorted array...
: leetcode上程序非常繁琐
: 大家有没有好的解法？
: thanks
相关阅读
加州27嵗剛畢業碩士男尋找有緣485女 (转载)冬奥会俄语常用语Re: 才明白为什么OB能从大银行募集十亿多的竞选经费 (转载)昨晚去一个小留家开新帖 排顺序蕲春县公安局副局长嫁女收取下属94人礼金46900元被免职！ (转载)宁夏自治区党委书记、主席带头扫雪铲冰装逼进化史MIT索男轻松双飞俩性感白妞 ,扬我国威(图) (转载)今天写诗发包子，发写的好的前三个子怡现场测智商情商，结果惊人印度一艘登陆舰搁浅 两月内连续事故已损七艘舰 (转载)1 米 2 的腿告诉你一个老印是怎么忽悠老美的真实故事(转载)士兵夜入暗室性侵女士官 打不过无奈求和 (转载)火车上的乘客师姐的车，成就了师弟的百年良缘 (转载)这题目我永远不会啊数学趣味题，尼玛能算的进来解题。 (转载)twitter名字里面X多的白女,不是pron star也是浪荡女