支持于洋这组运动员的，请到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
相关阅读
这首诗怎么样？为什么高速上面一边除了车祸，另外一个方向也要减速通过？ (转载)绳命，是剁么的回晃;绳命，是入刺的井猜老农水井打水打出怪物 (转载)快去看校花没事不要把照片放上网求P你想把美元兑换成日元么,我有一个最简便的办法这个朝代给后代留下的文物牛逼啊 (转载)我是不是想多了？ (转载)给你的美国朋友介绍个学中文的好网站河北高考得0分的作文 (转载)《非你莫属》张绍刚与转业军人唇枪舌剑，张绍刚完败！ (转载)西安水井那事情，视频来了，笑出六块腹肌啊说真的，老邢拉成过皮条么平均每位考生吃三盒饭，喝五瓶水。生死有命，富贵在天真心求建议，我和女友何去何从 (转载)我准备去taobao卖肉灵芝甩大便老爸你这是要闹哪样？！