S********g
发帖数: 45 | 1 至少以前是 现在不知道
Kth/median of 2 sorted array...
leetcode上程序非常繁琐
大家有没有好的解法？
thanks |
S********g
发帖数: 45 | 2 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*******m
发帖数: 457 | 3
黄蓉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
发帖数: 31 | 4 目前我能想到最好的建最小堆 (lgm+lgn)
当然了，建堆也需要时间的
【在 S********g 的大作中提到】
: 至少以前是 现在不知道
: Kth/median of 2 sorted array...
: leetcode上程序非常繁琐
: 大家有没有好的解法？
: thanks
|
w****x
发帖数: 2483 | 5
我这个id和黄蓉有半毛钱的关系吗 -_- , 彩虹mm?
【在 r*******m 的大作中提到】
:
: 黄蓉gg的啊。。。没仔细看啊，应该可以再优化一些吧。
: a,b每次应该都能减半的 O(logK)
|
t********e
发帖数: 344 | 6 觉得leetcode上的解挺intuitive的 也不复杂啊 二分法的idea |
p*****2
发帖数: 21240 | |
S********g
发帖数: 45 | 8 是啊 二爷一语中的。。
C里面可以array A＋i 好象java里面不行。。。
面试的时候可不可以 就这一道题用C写啊。。。。 |
l*****a
发帖数: 14598 | 9 你为什么这道会用C,别的题就不会用C ne
【在 S********g 的大作中提到】
: 是啊 二爷一语中的。。
: C里面可以array A＋i 好象java里面不行。。。
: 面试的时候可不可以 就这一道题用C写啊。。。。
|
g*****e
发帖数: 282 | 10 把首尾两个index都传进去就可以了
search(int[] a, int startA, int endA, int[] b, int startB, int endB)
【在 S********g 的大作中提到】
: 是啊 二爷一语中的。。
: C里面可以array A＋i 好象java里面不行。。。
: 面试的时候可不可以 就这一道题用C写啊。。。。
|
|
|
p*****2
发帖数: 21240 | 11
这道题我碰到过。在提示下给了一个思路，最后拿到offer了。面试的时候不一定要求
那么高。
这题如果没做过的话基本是做不出来。我以前在leetcode上扫了一眼，觉得面试不会出
这么变态的题。面试之前在glassdoor上看到这个公司出了几次这题，也没提起注意，
没想到还真给碰到了。
【在 S********g 的大作中提到】
: 是啊 二爷一语中的。。
: C里面可以array A＋i 好象java里面不行。。。
: 面试的时候可不可以 就这一道题用C写啊。。。。
|
p*****2
发帖数: 21240 | 12
以前写过，不好写。你有过了OJ的code吗？
【在 g*****e 的大作中提到】
: 把首尾两个index都传进去就可以了
: search(int[] a, int startA, int endA, int[] b, int startB, int endB)
|
w****x
发帖数: 2483 | 13
二爷威武啊~~~~
【在 p*****2 的大作中提到】
:
: 以前写过，不好写。你有过了OJ的code吗？
|
p*****2
发帖数: 21240 | 14
你是不是已经拿到了，怎么看不到你做题了。
【在 w****x 的大作中提到】
:
: 二爷威武啊~~~~
|
c********t
发帖数: 5706 | 15 也可以传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)
|
w***o
发帖数: 109 | 16 这是我见过的最精简的算法，可以用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;
} |
g*****e
发帖数: 282 | 17 我刚被storm8还是quantcast问了。。。
【在 S********g 的大作中提到】
: 至少以前是 现在不知道
: Kth/median of 2 sorted array...
: leetcode上程序非常繁琐
: 大家有没有好的解法？
: thanks
|
S********g
发帖数: 45 | 18 至少以前是 现在不知道
Kth/median of 2 sorted array...
leetcode上程序非常繁琐
大家有没有好的解法？
thanks |
S********g
发帖数: 45 | 19 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*******m
发帖数: 457 | 20
黄蓉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
发帖数: 31 | 21 目前我能想到最好的建最小堆 (lgm+lgn)
当然了，建堆也需要时间的
【在 S********g 的大作中提到】
: 至少以前是 现在不知道
: Kth/median of 2 sorted array...
: leetcode上程序非常繁琐
: 大家有没有好的解法？
: thanks
|
w****x
发帖数: 2483 | 22
我这个id和黄蓉有半毛钱的关系吗 -_- , 彩虹mm?
【在 r*******m 的大作中提到】
:
: 黄蓉gg的啊。。。没仔细看啊，应该可以再优化一些吧。
: a,b每次应该都能减半的 O(logK)
|
t********e
发帖数: 344 | 23 觉得leetcode上的解挺intuitive的 也不复杂啊 二分法的idea |
p*****2
发帖数: 21240 | |
S********g
发帖数: 45 | 25 是啊 二爷一语中的。。
C里面可以array A＋i 好象java里面不行。。。
面试的时候可不可以 就这一道题用C写啊。。。。 |
l*****a
发帖数: 14598 | 26 你为什么这道会用C,别的题就不会用C ne
【在 S********g 的大作中提到】
: 是啊 二爷一语中的。。
: C里面可以array A＋i 好象java里面不行。。。
: 面试的时候可不可以 就这一道题用C写啊。。。。
|
g*****e
发帖数: 282 | 27 把首尾两个index都传进去就可以了
search(int[] a, int startA, int endA, int[] b, int startB, int endB)
【在 S********g 的大作中提到】
: 是啊 二爷一语中的。。
: C里面可以array A＋i 好象java里面不行。。。
: 面试的时候可不可以 就这一道题用C写啊。。。。
|
p*****2
发帖数: 21240 | 28
这道题我碰到过。在提示下给了一个思路，最后拿到offer了。面试的时候不一定要求
那么高。
这题如果没做过的话基本是做不出来。我以前在leetcode上扫了一眼，觉得面试不会出
这么变态的题。面试之前在glassdoor上看到这个公司出了几次这题，也没提起注意，
没想到还真给碰到了。
【在 S********g 的大作中提到】
: 是啊 二爷一语中的。。
: C里面可以array A＋i 好象java里面不行。。。
: 面试的时候可不可以 就这一道题用C写啊。。。。
|
p*****2
发帖数: 21240 | 29
以前写过，不好写。你有过了OJ的code吗？
【在 g*****e 的大作中提到】
: 把首尾两个index都传进去就可以了
: search(int[] a, int startA, int endA, int[] b, int startB, int endB)
|
w****x
发帖数: 2483 | 30
二爷威武啊~~~~
【在 p*****2 的大作中提到】
:
: 以前写过，不好写。你有过了OJ的code吗？
|
|
|
p*****2
发帖数: 21240 | 31
你是不是已经拿到了，怎么看不到你做题了。
【在 w****x 的大作中提到】
:
: 二爷威武啊~~~~
|
c********t
发帖数: 5706 | 32 也可以传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)
|
w***o
发帖数: 109 | 33 这是我见过的最精简的算法，可以用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;
} |
g*****e
发帖数: 282 | 34 我刚被storm8还是quantcast问了。。。
【在 S********g 的大作中提到】
: 至少以前是 现在不知道
: Kth/median of 2 sorted array...
: leetcode上程序非常繁琐
: 大家有没有好的解法？
: thanks
|
l**b
发帖数: 457 | |
m******d
发帖数: 414 | 36 ft，我这次onsite也被问到了这题
【在 S********g 的大作中提到】
: 至少以前是 现在不知道
: Kth/median of 2 sorted array...
: leetcode上程序非常繁琐
: 大家有没有好的解法？
: thanks
|
