logo
Redian新闻
>未名空间
>JobHunting - 待字闺中
>
请教Find Median Of Two Sorted Arrays
avatar
请教Find Median Of Two Sorted Arrays# JobHunting - 待字闺中
C*U
1 楼
我把leetcode上好多例子拿到机器上测试了 都没出错
但是在leetcode上会time limit exceeded
应该是有一个死循环
我找不出来
double findMedian(int A[], int m, int B[], int n) {
if(!n) {
return (A[(m - 1)/ 2] + A[(m - 1)/ 2 + (m - 1) % 2]) / 2.0;
}
int aStart = -1, aEnd = (m + n - 1) / 2 - 1;
int bStart = -1, bEnd = 0;
while(true) {
if(bEnd + 1 < n && A[aEnd] <= B[bEnd + 1] && B[bEnd] <= A[aEnd + 1])
{
break;
}
if(bEnd == n - 1 && B[bEnd] <= A[aEnd + 1]) {
break;
}
if(A[aEnd] < B[bEnd]) {
aStart = aEnd;
aEnd = aEnd + (bEnd - bStart + 1) / 2;
bEnd = bEnd - (bEnd - bStart + 1) / 2;
}
else if(A[aEnd] == B[bEnd]) {
break;
}
else {
bStart = bEnd;
if(bEnd + (aEnd - aStart + 1) / 2 < n) {
bEnd = bEnd + (aEnd - aStart + 1) / 2;
aEnd = aEnd - (aEnd - aStart + 1) / 2;
}
else {
aEnd = aEnd - (n - 1 - bEnd);
bEnd = n - 1;
}
}
}
if((m + n) % 2) {
return A[aEnd] > B[bEnd] ? A[aEnd] : B[bEnd];
}
else {
if(aEnd == -1) {
return (B[n - 1] + A[0]) / 2.0;
}
if(bEnd == -1) {
return aEnd == m - 1 ? (A[m - 1] + B[0]) / 2.0 : (A[aEnd] + A[
aEnd + 1]) / 2.0;
}
if(bEnd == n - 1){
return (A[aEnd] + (A[aEnd + 1] > B[bEnd] ? A[aEnd + 1] : B[bEnd]
)) / 2.0;
}
return ((A[aEnd] > B[bEnd] ? A[aEnd] : B[bEnd]) + (A[aEnd + 1] < B[
bEnd + 1] ? A[aEnd + 1] : B[bEnd + 1])) / 2.0;
}
}
double findMedianSortedArrays(int A[], int m, int B[], int n) {
if(m >= n) {
return findMedian(A, m, B, n);
}
else {
return findMedian(B, n, A, m);
}
}
avatar
w*x
2 楼
这题skip掉吧
avatar
C*U
3 楼
恩 刚才检查了半个小时 通过测试 总算把错误找出来了
这题目面试如果要写 必挂无疑啊！

【在 w****x 的大作中提到】
: 这题skip掉吧
avatar
p*2
4 楼
这题太难。C还要好写一些。Java不容易。
avatar
C*U
5 楼
我用c++的 不过你看我的code写的很难看。。。。

【在 p*****2 的大作中提到】
: 这题太难。C还要好写一些。Java不容易。
avatar
p*2
6 楼

C＋＋应该能写的更简洁。

【在 C***U 的大作中提到】
: 我用c++的 不过你看我的code写的很难看。。。。
avatar
C*U
7 楼
恩 我是初学者
所以还没有经验
希望能指点我一二

【在 p*****2 的大作中提到】
:
: C＋＋应该能写的更简洁。
avatar
p*2
8 楼

我C＋＋不懂，问上边的大牛吧。我上次用Java写的惨不忍睹呀。

【在 C***U 的大作中提到】
: 恩 我是初学者
: 所以还没有经验
: 希望能指点我一二
avatar
B*1
9 楼
My code, pass all the test.
double findKth(int a[], int m, int b[], int n, int k)
{
if (m > n) return findKth(b, n, a, m, k);
if (m == 0) return b[k-1];
if (k == 1) return min(a[0], b[0]);
int pa = min(k/2, m), pb = k - pa;
if (a[pa-1] < b[pb-1]) return findKth(a+pa, m-pa, b, n, k - pa);
return findKth(a, m, b+pb, n-pb, k-pb);
}
class Solution {
public:
double findMedianSortedArrays(int A[], int m, int B[], int n) {
int total = m+n;
if (total&0x1)
return findKth(A, m, B, n, total/2+1);
else
return (findKth(A, m, B, n, total/2) + findKth(A, m, B, n, total/2+1
))/2;
}
};

【在 C***U 的大作中提到】
: 我把leetcode上好多例子拿到机器上测试了 都没出错
: 但是在leetcode上会time limit exceeded
: 应该是有一个死循环
: 我找不出来
: double findMedian(int A[], int m, int B[], int n) {
: if(!n) {
: return (A[(m - 1)/ 2] + A[(m - 1)/ 2 + (m - 1) % 2]) / 2.0;
: }
: int aStart = -1, aEnd = (m + n - 1) / 2 - 1;
: int bStart = -1, bEnd = 0;
avatar
p*2
10 楼

貌似玄铁的算法？

【在 B*******1 的大作中提到】
: My code, pass all the test.
: double findKth(int a[], int m, int b[], int n, int k)
: {
: if (m > n) return findKth(b, n, a, m, k);
: if (m == 0) return b[k-1];
: if (k == 1) return min(a[0], b[0]);
: int pa = min(k/2, m), pb = k - pa;
: if (a[pa-1] < b[pb-1]) return findKth(a+pa, m-pa, b, n, k - pa);
: return findKth(a, m, b+pb, n-pb, k-pb);
: }
avatar
B*1
11 楼
是啊，学习大牛得。

【在 p*****2 的大作中提到】
:
: 貌似玄铁的算法？
avatar
C*U
12 楼
恩 用递归不错 果然好写好多
膜拜你
不过我最近想练习尽量不用递归。。。

【在 B*******1 的大作中提到】
: My code, pass all the test.
: double findKth(int a[], int m, int b[], int n, int k)
: {
: if (m > n) return findKth(b, n, a, m, k);
: if (m == 0) return b[k-1];
: if (k == 1) return min(a[0], b[0]);
: int pa = min(k/2, m), pb = k - pa;
: if (a[pa-1] < b[pb-1]) return findKth(a+pa, m-pa, b, n, k - pa);
: return findKth(a, m, b+pb, n-pb, k-pb);
: }
avatar
p*2
13 楼

牛逼呀。膜拜一下。

【在 B*******1 的大作中提到】
: 是啊，学习大牛得。
avatar
C*U
14 楼
我做leetcode前一半用递归。。。然后被我同学鄙视了
后一半我就不用递归了。。。嘎嘎

【在 p*****2 的大作中提到】
:
: 牛逼呀。膜拜一下。
avatar
p*2
15 楼

不要死较真。看题。这题写成这样已经很牛逼了。我同样的算法用Java写，难写很多。
因为没有指针的灵活性。

【在 C***U 的大作中提到】
: 恩 用递归不错 果然好写好多
: 膜拜你
: 不过我最近想练习尽量不用递归。。。
avatar
w*x
16 楼
对阿， median of 2 sorted array 就是kth element of two sorted array的变体，
后者简洁多了， 但是收敛速度不一样啊
avatar
C*U
17 楼
好 明白了
哈哈哈
他写的code确实很牛 那么短！

【在 p*****2 的大作中提到】
:
: 不要死较真。看题。这题写成这样已经很牛逼了。我同样的算法用Java写，难写很多。
: 因为没有指针的灵活性。
avatar
D*3
18 楼
这题leetcode有问题，我直接打public class Solution {
public double findMedianSortedArrays(int A[], int B[]) {
return 0;
}
}
他说我超时。。。他扯淡吧
avatar
p*2
19 楼

总是这样吗？有的时候人多会这样。

【在 D****3 的大作中提到】
: 这题leetcode有问题，我直接打public class Solution {
: public double findMedianSortedArrays(int A[], int B[]) {
: return 0;
: }
: }
: 他说我超时。。。他扯淡吧
avatar
C*U
20 楼
那应该是人品问题 哈哈哈
有时候他可能在维护什么的吧？

【在 D****3 的大作中提到】
: 这题leetcode有问题，我直接打public class Solution {
: public double findMedianSortedArrays(int A[], int B[]) {
: return 0;
: }
: }
: 他说我超时。。。他扯淡吧
avatar
e*s
21 楼
LeetCode上这题的OJ很奇怪，O(n)居然能过Large case
avatar
C*U
22 楼
我把leetcode上好多例子拿到机器上测试了 都没出错
但是在leetcode上会time limit exceeded
应该是有一个死循环
我找不出来
double findMedian(int A[], int m, int B[], int n) {
if(!n) {
return (A[(m - 1)/ 2] + A[(m - 1)/ 2 + (m - 1) % 2]) / 2.0;
}
int aStart = -1, aEnd = (m + n - 1) / 2 - 1;
int bStart = -1, bEnd = 0;
while(true) {
if(bEnd + 1 < n && A[aEnd] <= B[bEnd + 1] && B[bEnd] <= A[aEnd + 1])
{
break;
}
if(bEnd == n - 1 && B[bEnd] <= A[aEnd + 1]) {
break;
}
if(A[aEnd] < B[bEnd]) {
aStart = aEnd;
aEnd = aEnd + (bEnd - bStart + 1) / 2;
bEnd = bEnd - (bEnd - bStart + 1) / 2;
}
else if(A[aEnd] == B[bEnd]) {
break;
}
else {
bStart = bEnd;
if(bEnd + (aEnd - aStart + 1) / 2 < n) {
bEnd = bEnd + (aEnd - aStart + 1) / 2;
aEnd = aEnd - (aEnd - aStart + 1) / 2;
}
else {
aEnd = aEnd - (n - 1 - bEnd);
bEnd = n - 1;
}
}
}
if((m + n) % 2) {
return A[aEnd] > B[bEnd] ? A[aEnd] : B[bEnd];
}
else {
if(aEnd == -1) {
return (B[n - 1] + A[0]) / 2.0;
}
if(bEnd == -1) {
return aEnd == m - 1 ? (A[m - 1] + B[0]) / 2.0 : (A[aEnd] + A[
aEnd + 1]) / 2.0;
}
if(bEnd == n - 1){
return (A[aEnd] + (A[aEnd + 1] > B[bEnd] ? A[aEnd + 1] : B[bEnd]
)) / 2.0;
}
return ((A[aEnd] > B[bEnd] ? A[aEnd] : B[bEnd]) + (A[aEnd + 1] < B[
bEnd + 1] ? A[aEnd + 1] : B[bEnd + 1])) / 2.0;
}
}
double findMedianSortedArrays(int A[], int m, int B[], int n) {
if(m >= n) {
return findMedian(A, m, B, n);
}
else {
return findMedian(B, n, A, m);
}
}
avatar
w*x
23 楼
这题skip掉吧
avatar
C*U
24 楼
恩 刚才检查了半个小时 通过测试 总算把错误找出来了
这题目面试如果要写 必挂无疑啊！

【在 w****x 的大作中提到】
: 这题skip掉吧
avatar
p*2
25 楼
这题太难。C还要好写一些。Java不容易。
avatar
C*U
26 楼
我用c++的 不过你看我的code写的很难看。。。。

【在 p*****2 的大作中提到】
: 这题太难。C还要好写一些。Java不容易。
avatar
p*2
27 楼

C＋＋应该能写的更简洁。

【在 C***U 的大作中提到】
: 我用c++的 不过你看我的code写的很难看。。。。
avatar
C*U
28 楼
恩 我是初学者
所以还没有经验
希望能指点我一二

【在 p*****2 的大作中提到】
:
: C＋＋应该能写的更简洁。
avatar
p*2
29 楼

我C＋＋不懂，问上边的大牛吧。我上次用Java写的惨不忍睹呀。

【在 C***U 的大作中提到】
: 恩 我是初学者
: 所以还没有经验
: 希望能指点我一二
avatar
B*1
30 楼
My code, pass all the test.
double findKth(int a[], int m, int b[], int n, int k)
{
if (m > n) return findKth(b, n, a, m, k);
if (m == 0) return b[k-1];
if (k == 1) return min(a[0], b[0]);
int pa = min(k/2, m), pb = k - pa;
if (a[pa-1] < b[pb-1]) return findKth(a+pa, m-pa, b, n, k - pa);
return findKth(a, m, b+pb, n-pb, k-pb);
}
class Solution {
public:
double findMedianSortedArrays(int A[], int m, int B[], int n) {
int total = m+n;
if (total&0x1)
return findKth(A, m, B, n, total/2+1);
else
return (findKth(A, m, B, n, total/2) + findKth(A, m, B, n, total/2+1
))/2;
}
};

【在 C***U 的大作中提到】
: 我把leetcode上好多例子拿到机器上测试了 都没出错
: 但是在leetcode上会time limit exceeded
: 应该是有一个死循环
: 我找不出来
: double findMedian(int A[], int m, int B[], int n) {
: if(!n) {
: return (A[(m - 1)/ 2] + A[(m - 1)/ 2 + (m - 1) % 2]) / 2.0;
: }
: int aStart = -1, aEnd = (m + n - 1) / 2 - 1;
: int bStart = -1, bEnd = 0;
avatar
p*2
31 楼

貌似玄铁的算法？

【在 B*******1 的大作中提到】
: My code, pass all the test.
: double findKth(int a[], int m, int b[], int n, int k)
: {
: if (m > n) return findKth(b, n, a, m, k);
: if (m == 0) return b[k-1];
: if (k == 1) return min(a[0], b[0]);
: int pa = min(k/2, m), pb = k - pa;
: if (a[pa-1] < b[pb-1]) return findKth(a+pa, m-pa, b, n, k - pa);
: return findKth(a, m, b+pb, n-pb, k-pb);
: }
avatar
B*1
32 楼
是啊，学习大牛得。

【在 p*****2 的大作中提到】
:
: 貌似玄铁的算法？
avatar
C*U
33 楼
恩 用递归不错 果然好写好多
膜拜你
不过我最近想练习尽量不用递归。。。

【在 B*******1 的大作中提到】
: My code, pass all the test.
: double findKth(int a[], int m, int b[], int n, int k)
: {
: if (m > n) return findKth(b, n, a, m, k);
: if (m == 0) return b[k-1];
: if (k == 1) return min(a[0], b[0]);
: int pa = min(k/2, m), pb = k - pa;
: if (a[pa-1] < b[pb-1]) return findKth(a+pa, m-pa, b, n, k - pa);
: return findKth(a, m, b+pb, n-pb, k-pb);
: }
avatar
p*2
34 楼

牛逼呀。膜拜一下。

【在 B*******1 的大作中提到】
: 是啊，学习大牛得。
avatar
C*U
35 楼
我做leetcode前一半用递归。。。然后被我同学鄙视了
后一半我就不用递归了。。。嘎嘎

【在 p*****2 的大作中提到】
:
: 牛逼呀。膜拜一下。
avatar
p*2
36 楼

不要死较真。看题。这题写成这样已经很牛逼了。我同样的算法用Java写，难写很多。
因为没有指针的灵活性。

【在 C***U 的大作中提到】
: 恩 用递归不错 果然好写好多
: 膜拜你
: 不过我最近想练习尽量不用递归。。。
avatar
w*x
37 楼
对阿， median of 2 sorted array 就是kth element of two sorted array的变体，
后者简洁多了， 但是收敛速度不一样啊
avatar
C*U
38 楼
好 明白了
哈哈哈
他写的code确实很牛 那么短！

【在 p*****2 的大作中提到】
:
: 不要死较真。看题。这题写成这样已经很牛逼了。我同样的算法用Java写，难写很多。
: 因为没有指针的灵活性。
avatar
D*3
39 楼
这题leetcode有问题，我直接打public class Solution {
public double findMedianSortedArrays(int A[], int B[]) {
return 0;
}
}
他说我超时。。。他扯淡吧
avatar
p*2
40 楼

总是这样吗？有的时候人多会这样。

【在 D****3 的大作中提到】
: 这题leetcode有问题，我直接打public class Solution {
: public double findMedianSortedArrays(int A[], int B[]) {
: return 0;
: }
: }
: 他说我超时。。。他扯淡吧
avatar
C*U
41 楼
那应该是人品问题 哈哈哈
有时候他可能在维护什么的吧？

【在 D****3 的大作中提到】
: 这题leetcode有问题，我直接打public class Solution {
: public double findMedianSortedArrays(int A[], int B[]) {
: return 0;
: }
: }
: 他说我超时。。。他扯淡吧
avatar
e*s
42 楼
LeetCode上这题的OJ很奇怪，O(n)居然能过Large case
avatar
Y*f
43 楼
刚做了这道题，leetcode上为了不调用find kth elments两次写了一个比较复杂的。我
写了一个稍微简单点的，实际上也是基于find kth element.
double median2Array(int* arrA, int lenA, int* arrB, int lenB, int k, int
isEven)
{
if (lenA == 0)
return isEven ? (arrB[k-1] + arrB[k]) / 2.0 : arrB[k-1];
else if (lenB == 0)
return isEven ? (arrA[k-1] + arrA[k]) / 2.0 : arrA[k-1];
else if (k == 1)
{
vector vect(min(2, lenA) + min(2, lenB));
copy(arrA, arrA + min(2, lenA), vect.begin());
copy(arrB, arrB + min(2, lenB), vect.begin() + lenA);
sort(vect.begin(), vect.end());
return (isEven ? (vect[0] + vect[1]) / 2.0 : vect[0]);
}
int midA = (min(lenA, k) - 1) / 2;
int midB = (min(lenB, k) - 1) / 2;
if (arrA[midA] < arrB[midB])
return median2Array(arrA + midA + 1, lenA - midA - 1, arrB, lenB, k
- midA - 1, isEven);
else
return median2Array(arrA, lenA, arrB + midB + 1, lenB - midB - 1, k
- midB - 1, isEven);
}
double median2Array(int* arrA, int lenA, int* arrB, int lenB)
{
int isEven = ((lenA + lenB) % 2) ? 0 : 1;
return median2Array(arrA, lenA, arrB, lenB, (lenA + lenB + 1) / 2,
isEven);
}

【在 C***U 的大作中提到】
: 我把leetcode上好多例子拿到机器上测试了 都没出错
: 但是在leetcode上会time limit exceeded
: 应该是有一个死循环
: 我找不出来
: double findMedian(int A[], int m, int B[], int n) {
: if(!n) {
: return (A[(m - 1)/ 2] + A[(m - 1)/ 2 + (m - 1) % 2]) / 2.0;
: }
: int aStart = -1, aEnd = (m + n - 1) / 2 - 1;
: int bStart = -1, bEnd = 0;
avatar
b*m
44 楼

代码我虽然看懂了，但是能不能说说思想？

【在 B*******1 的大作中提到】
: My code, pass all the test.
: double findKth(int a[], int m, int b[], int n, int k)
: {
: if (m > n) return findKth(b, n, a, m, k);
: if (m == 0) return b[k-1];
: if (k == 1) return min(a[0], b[0]);
: int pa = min(k/2, m), pb = k - pa;
: if (a[pa-1] < b[pb-1]) return findKth(a+pa, m-pa, b, n, k - pa);
: return findKth(a, m, b+pb, n-pb, k-pb);
: }
avatar
b*m
45 楼

其实思想我也大概明白了，就是不断把k减半进行收敛，最后达到两条退出条件之一（m
==0或者k==1），而决定后续递归的参数传入条件就是pa和pb点的选取以及比较。

【在 b***m 的大作中提到】
:
: 代码我虽然看懂了，但是能不能说说思想？
avatar
Y*f
46 楼
刚做了这道题，leetcode上为了不调用find kth elments两次写了一个比较复杂的。我
写了一个稍微简单点的，实际上也是基于find kth element.
double median2Array(int* arrA, int lenA, int* arrB, int lenB, int k, int
isEven)
{
if (lenA == 0)
return isEven ? (arrB[k-1] + arrB[k]) / 2.0 : arrB[k-1];
else if (lenB == 0)
return isEven ? (arrA[k-1] + arrA[k]) / 2.0 : arrA[k-1];
else if (k == 1)
{
vector vect(min(2, lenA) + min(2, lenB));
copy(arrA, arrA + min(2, lenA), vect.begin());
copy(arrB, arrB + min(2, lenB), vect.begin() + lenA);
sort(vect.begin(), vect.end());
return (isEven ? (vect[0] + vect[1]) / 2.0 : vect[0]);
}
int midA = (min(lenA, k) - 1) / 2;
int midB = (min(lenB, k) - 1) / 2;
if (arrA[midA] < arrB[midB])
return median2Array(arrA + midA + 1, lenA - midA - 1, arrB, lenB, k
- midA - 1, isEven);
else
return median2Array(arrA, lenA, arrB + midB + 1, lenB - midB - 1, k
- midB - 1, isEven);
}
double median2Array(int* arrA, int lenA, int* arrB, int lenB)
{
int isEven = ((lenA + lenB) % 2) ? 0 : 1;
return median2Array(arrA, lenA, arrB, lenB, (lenA + lenB + 1) / 2,
isEven);
}

【在 C***U 的大作中提到】
: 我把leetcode上好多例子拿到机器上测试了 都没出错
: 但是在leetcode上会time limit exceeded
: 应该是有一个死循环
: 我找不出来
: double findMedian(int A[], int m, int B[], int n) {
: if(!n) {
: return (A[(m - 1)/ 2] + A[(m - 1)/ 2 + (m - 1) % 2]) / 2.0;
: }
: int aStart = -1, aEnd = (m + n - 1) / 2 - 1;
: int bStart = -1, bEnd = 0;
avatar
b*m
47 楼

代码我虽然看懂了，但是能不能说说思想？

【在 B*******1 的大作中提到】
: My code, pass all the test.
: double findKth(int a[], int m, int b[], int n, int k)
: {
: if (m > n) return findKth(b, n, a, m, k);
: if (m == 0) return b[k-1];
: if (k == 1) return min(a[0], b[0]);
: int pa = min(k/2, m), pb = k - pa;
: if (a[pa-1] < b[pb-1]) return findKth(a+pa, m-pa, b, n, k - pa);
: return findKth(a, m, b+pb, n-pb, k-pb);
: }
avatar
b*m
48 楼

其实思想我也大概明白了，就是不断把k减半进行收敛，最后达到两条退出条件之一（m
==0或者k==1），而决定后续递归的参数传入条件就是pa和pb点的选取以及比较。

【在 b***m 的大作中提到】
:
: 代码我虽然看懂了，但是能不能说说思想？
avatar
w*j
49 楼
logk啊，不要再看lgm + lgn的了
相关阅读
这个Offer有没有希望？因为国际学生身份offer被取消，可以打官司吗？看几年前的google面经有感Uber真的完了:Uber insurance bill passes Senate (转载)H1b approvedG家 export control questionnairePinterest Software Engineer position for Data/Hadoop大量放老印进入米国的法案都是哪些政客支持？【工作机会】Senior Software Engineer 加州南湾关于deemed exports license所谓工作经验Offer 求比较话说单身男不适合去加州吧问一个机器学习的问题在Facebook做广告纯属浪费钱Google Research Scientistnon pp Adv H1b 是不是没戏了！G家如何和hr商量工作地点NON-PP ADV H1B CSCRe: 五月五号新书预告：克灵顿的现金 (转载)
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。