把问题简化吧，找2个sorted array的median - JobHunting版

本页内容为未名空间相应帖子的节选和存档，一周内的贴子最多显示50字，超过一周显示500字访问原贴

JobHunting版 - 把问题简化吧，找2个sorted array的median

相关主题
● Find Median Of Two Sorted Arrays
● 求两个有序数组的median的平凡解法?
● 请帖个Median of Two Sorted Arrays的好解法？
● 贡献一个Median of two sorted arrays的java code
● 百思不得其解的一道题目
● 跪了，Median of Two Sorted Arrays 问题求解
● 这个题目的比较好的方法是什么？
● Median of Two Sorted Arrays
● 为什么我的这个dynamic解法有错误
● 问道小学题：两等长有序数组，求第k个数

相关话题的讨论汇总
话题: int话题: return话题: mid话题: else话题: double

进入JobHunting版参与讨论

(共1页)

b***m
发帖数: 5987

我记得上次有人发过一个很好的代码，但是我找不到了，貌似是C++递归实现的，代码
很短，应该只有十几行，没有用min-heap的。

c********t
发帖数: 5706

quicksort? 与求kth in two sorted array 一样吧？

【在 b***m 的大作中提到】

: 我记得上次有人发过一个很好的代码，但是我找不到了，貌似是C++递归实现的，代码
: 很短，应该只有十几行，没有用min-heap的。

b***m
发帖数: 5987

对，意思差不多。我记得那个做法没有用quicksort，是类似于二分？

【在 c********t 的大作中提到】

: quicksort? 与求kth in two sorted array 一样吧？

l*****a
发帖数: 14598

这题没法简化
数组长度不一
长度奇偶不定
边界点很难确定的
思路倒是简单，就是两分，然后每次抛掉肯定用不到的部分

【在 b***m 的大作中提到】

: 我记得上次有人发过一个很好的代码，但是我找不到了，貌似是C++递归实现的，代码
: 很短，应该只有十几行，没有用min-heap的。

f*****e
发帖数: 2992

用短array的median去分离长的，然后recurse。

【在 b***m 的大作中提到】

: 我记得上次有人发过一个很好的代码，但是我找不到了，貌似是C++递归实现的，代码
: 很短，应该只有十几行，没有用min-heap的。

b***m
发帖数: 5987

取两个数组各自的median，比较大小，然后把小的左边抛弃，大的右边抛弃，再继续取
median，如此反复？

【在 l*****a 的大作中提到】

: 这题没法简化
: 数组长度不一
: 长度奇偶不定
: 边界点很难确定的
: 思路倒是简单，就是两分，然后每次抛掉肯定用不到的部分

b***m
发帖数: 5987

什么叫做分离长的？

【在 f*****e 的大作中提到】

: 用短array的median去分离长的，然后recurse。

f*****e
发帖数: 2992

给定两个arrays，有一个长，有一个短，然后
就是找短array的median在长array中的位置啊，耗时O(lg(size of long array))。
然后继续recurse。

【在 b***m 的大作中提到】

:
: 什么叫做分离长的？

b***m
发帖数: 5987

找到之后呢？

【在 f*****e 的大作中提到】

: 给定两个arrays，有一个长，有一个短，然后
: 就是找短array的median在长array中的位置啊，耗时O(lg(size of long array))。
: 然后继续recurse。

l*****a
发帖数: 14598

大的右边似乎只抛掉小的左边那么长，保证对称。。
基本就这个思路

【在 b***m 的大作中提到】

:
: 找到之后呢？

相关主题
● 贡献一个Median of two sorted arrays的java code
● 百思不得其解的一道题目
● 跪了，Median of Two Sorted Arrays 问题求解
● 这个题目的比较好的方法是什么？
进入JobHunting版参与讨论

O******i
发帖数: 269

都拿到大卧佛了还子孜孜不倦做题啊?
这题从来没看过是很难想到log(N）的解法的，我第一次面M的SDET的时候陪吃午饭的阿
三就问的，尼玛，SDET1至于要问这么难的题么?

【在 b***m 的大作中提到】

: 我记得上次有人发过一个很好的代码，但是我找不到了，貌似是C++递归实现的，代码
: 很短，应该只有十几行，没有用min-heap的。

f*****e
发帖数: 2992

然后就继续recurse，新的arrays长短就不一定了。

【在 b***m 的大作中提到】

:
: 找到之后呢？

b***m
发帖数: 5987

哦，对，好像貌似是这么个意思，我有点儿印象了……

【在 l*****a 的大作中提到】

: 大的右边似乎只抛掉小的左边那么长，保证对称。。
: 基本就这个思路

b***m
发帖数: 5987

做着玩玩嘛，反正最近闲着也是闲着。面SDET1问这种题确实是吃饱了撑的。

【在 O******i 的大作中提到】

: 都拿到大卧佛了还子孜孜不倦做题啊?
: 这题从来没看过是很难想到log(N）的解法的，我第一次面M的SDET的时候陪吃午饭的阿
: 三就问的，尼玛，SDET1至于要问这么难的题么?

C***U
发帖数: 2406

01 double findKth(int a[], int m, int b[], int n, int k)
02 {
03 if (m > n) return findKth(b, n, a, m, k);
04
05 if (m == 0)
06 return b[k-1];
07
08 if (k == 1)
09 return min(a[0], b[0]);
10
11 int pa = min(k/2, m), pb = k - pa;
12
13 if (a[pa-1] < b[pb-1])
14 return findKth(a+pa, m-pa, b, n, k - pa);
15 else
16 return findKth(a, m, b+pb, n-pb, k-pb);
17 }
18
19 double findMedianSortedArrays(int A[], int m, int B[], int n) {
20 int total = m+n;
21
22 if (total&0x1)
23 return findKth(A, m, B, n, total/2+1);
24 else
25 return (findKth(A, m, B, n, total/2) + findKth(A, m, B, n,
total/2+1))/2;
26 }

【在 b***m 的大作中提到】

:
: 做着玩玩嘛，反正最近闲着也是闲着。面SDET1问这种题确实是吃饱了撑的。

O******i
发帖数: 269

其实先考虑两个数组等长的特殊情况，那个的递归log(N)解法比较好懂。
不等长就更难些。

【在 b***m 的大作中提到】

:
: 做着玩玩嘛，反正最近闲着也是闲着。面SDET1问这种题确实是吃饱了撑的。

b***m
发帖数: 5987

嗯，对，就是它，这个要收藏。

【在 C***U 的大作中提到】

: 01 double findKth(int a[], int m, int b[], int n, int k)
: 02 {
: 03 if (m > n) return findKth(b, n, a, m, k);
: 04
: 05 if (m == 0)
: 06 return b[k-1];
: 07
: 08 if (k == 1)
: 09 return min(a[0], b[0]);
: 10

O******i
发帖数: 269

华丽丽的先提升到一般解法(求kth)，进而轻松推出特殊解(k=中数)
问这题的面官肯定一看就知道是见过题的

【在 b***m 的大作中提到】

:
: 嗯，对，就是它，这个要收藏。

b***m
发帖数: 5987

真要用通用解法做这题就是给自己找麻烦，坛上某人已经吃过亏了。

【在 O******i 的大作中提到】

: 华丽丽的先提升到一般解法(求kth)，进而轻松推出特殊解(k=中数)
: 问这题的面官肯定一看就知道是见过题的

O******i
发帖数: 269

再问这题我就说见过，知道华丽解法，请君换题。

【在 b***m 的大作中提到】

:
: 真要用通用解法做这题就是给自己找麻烦，坛上某人已经吃过亏了。

相关主题
● Median of Two Sorted Arrays
● 为什么我的这个dynamic解法有错误
● 问道小学题：两等长有序数组，求第k个数
● 问道算法题
进入JobHunting版参与讨论

l*******b
发帖数: 2586

这个递归写得好简洁呀。。。贴个自己写的，这题总觉得边界情况太复杂
double find_medium(int A[], int m, int B[], int n) {
int flag = (m + n) % 2;
int k = (m + n) /2;
if(flag)
return one_side_k(A,m,B,n,k) | one_side_k(B,n,A,m,k);
else
return ((double)(one_side_k(A,m,B,n,k-1) | one_side_k(B,n,A,m,k-
1))
+ (one_side_k(A,m,B,n,k) | one_side_k(B,n,A,m,k))) /2;
}
int one_side_k(int A[], int m, int B[], int n, int k){
if(0 == n) return A[k];
int l,r, mid, cr;
l = 0, r = m - 1;
while(l <= r) {
mid = (l+r) /2;
cr = k-mid - 1;
if(cr < -1)
r = mid - 1;
else if(cr + 1 > n)
l = mid + 1;
else if(cr == -1) {
if(A[mid] <= B[0])
return A[mid];
r = mid - 1;
}
else if(cr + 1 == n) {
if(A[mid] >= B[n-1])
return A[mid];
l = mid + 1;
}
else if(A[mid] > B[cr+1])
r = mid - 1;
else if(A[mid] < B[cr])
l = mid + 1;
else
return A[mid];
}
return 0;
}

O******i
发帖数: 269

其实就是O(m+n)的解法，也不容易bug free, 小心数组越界。

k-

【在 l*******b 的大作中提到】

: 这个递归写得好简洁呀。。。贴个自己写的，这题总觉得边界情况太复杂
: double find_medium(int A[], int m, int B[], int n) {
: int flag = (m + n) % 2;
: int k = (m + n) /2;
: if(flag)
: return one_side_k(A,m,B,n,k) | one_side_k(B,n,A,m,k);
: else
: return ((double)(one_side_k(A,m,B,n,k-1) | one_side_k(B,n,A,m,k-
: 1))
: + (one_side_k(A,m,B,n,k) | one_side_k(B,n,A,m,k))) /2;

l*******b
发帖数: 2586

嗯，想法其实挺直观的，在一个数组里做binary search，不过类似binary search的好
像都挺难bug free的

【在 O******i 的大作中提到】

: 其实就是O(m+n)的解法，也不容易bug free, 小心数组越界。
:
: k-

O******i
发帖数: 269

阿三可能就想看一个O(m+n）的简单解法，不过就那样我当时也没有写好，下标有越界
。我是后来才知道有O(log(m+n))的解法，这题好像是CLRS的课后习题。

【在 b***m 的大作中提到】

:
: 真要用通用解法做这题就是给自己找麻烦，坛上某人已经吃过亏了。

b***m
发帖数: 5987

试着写了一下，还真不好写，边界条件比较多。

r****m
发帖数: 70

twitter电面被这道题搞挂

h****n
发帖数: 1093

你刚刚收藏的那个解法就是用通用解法来搞的
谁能贴一个不通过kth那个函数直接搞的log(m)+log(n)的简洁代码？

【在 b***m 的大作中提到】

: 试着写了一下，还真不好写，边界条件比较多。

Q*******e
发帖数: 939

这种问题如果没有见过,仔细想一下
当场就能写出bug free优化算法的, 算面试战斗机了.

l*******b
发帖数: 2586

偶数的时候有４种情况low_median和high_median分别在A或者Ｂ中。verify这个就得多
写好几句。感觉

【在 h****n 的大作中提到】

: 你刚刚收藏的那个解法就是用通用解法来搞的
: 谁能贴一个不通过kth那个函数直接搞的log(m)+log(n)的简洁代码？

l*******b
发帖数: 2586

最近翻的两本算法书上这个都是习题。应该算标准知识了

【在 Q*******e 的大作中提到】

: 这种问题如果没有见过,仔细想一下
: 当场就能写出bug free优化算法的, 算面试战斗机了.

相关主题
● median of two sorted arrays的时间复杂度(附上了过了oj的代码）
● find median for k sorted arrays
● 问一道google的题
● 找第K个最小的元素
进入JobHunting版参与讨论

c*****a
发帖数: 808

我的不简洁了.....brute force.....
面试肯定fail
public class Solution {
public double findMedianSortedArrays(int A[], int B[]) {
// Start typing your Java solution below
// DO NOT write main() function
if(A.length==0){
if(B.length % 2 ==1)
return (double) B[B.length/2];
else
return (double)(B[B.length/2] + B[B.length/2-1]) /2;
}
if(B.length ==0){
if(A.length % 2 ==1)
return (double)A[A.length/2];
else
return (double)(A[A.length/2] + A[A.length/2-1]) /2;
}
int total = A.length + B.length;
double ar[]= new double[2];
int mid = total /2;
int j=0; //always 0 and 1;
int Ahead = 0, Bhead = 0;
for(int i=0; i< mid+1; i++){
if(Ahead == A.length){
if(j>1)
j=0;
ar[j] =B[Bhead];
j++;
Bhead++;
}
else if(Bhead == B.length ){
if(j>1)
j=0;
ar[j] = A[Ahead];
j++;
Ahead++;
}
else
if(A[Ahead] if(j>1)
j=0;
ar[j] = A[Ahead];
j++;
Ahead++;
}
else{
if(j>1)
j=0;
ar[j] =B[Bhead];
j++;
Bhead++;
}

}
if(total % 2 == 0)
return (ar[0]+ ar[1]) /2;
else {
if(j==1)
return ar[0];
else
return ar[1];
}
}
}

c*****a
发帖数: 808

有java版吗....

【在 C***U 的大作中提到】

c**s
发帖数: 159

贴一个我写的：
class Solution {
public:
int kthsmallest(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 (a[0] < b[0])?a[0]:b[0];
}
if (k == m + n) {
return (a[m - 1] > b[n - 1])?a[m - 1]:b[n - 1];
}
int i = ((double) m) / (m + n) * (k - 1), j = k - 1 - i;
if (j >= n) {
j = n - 1;
i = k - n;
}
if (((i == 0) || (a[i - 1] <= b[j])) && (b[j] <= a[i])) {
return b[j];
}
if (((j == 0) || (b[j - 1] <= a[i])) && (a[i] <= b[j])) {
return a[i];
}
return (a[i] <= b[j])?kthsmallest(a + i + 1, m - i - 1, b, j, k - i
- 1):kthsmallest(a, i, b + j + 1, n - j - 1, k - j - 1);

}
double findMedianSortedArrays(int A[], int m, int B[], int n) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int temp = m + n;
return (temp & 1)?kthsmallest(A, m, B, n , (temp + 1) >> 1):((
kthsmallest(A, m ,B ,n , temp >> 1) + kthsmallest(A, m ,B, n, (temp >> 1) +
1)) * .5);

}
};

e******o
发帖数: 757

这个kth的要比找median 的容易写。median 还要考虑个数是奇数偶数之类的

【在 O******i 的大作中提到】

: 华丽丽的先提升到一般解法(求kth)，进而轻松推出特殊解(k=中数)
: 问这题的面官肯定一看就知道是见过题的

b***m
发帖数: 5987

对，是哦，我试着写了一下，思想虽然懂，代码还挺麻烦的。

【在 e******o 的大作中提到】

: 这个kth的要比找median 的容易写。median 还要考虑个数是奇数偶数之类的

b***m
发帖数: 5987

我记得上次有人发过一个很好的代码，但是我找不到了，貌似是C++递归实现的，代码
很短，应该只有十几行，没有用min-heap的。

c********t
发帖数: 5706

quicksort? 与求kth in two sorted array 一样吧？

【在 b***m 的大作中提到】

: 我记得上次有人发过一个很好的代码，但是我找不到了，貌似是C++递归实现的，代码
: 很短，应该只有十几行，没有用min-heap的。

b***m
发帖数: 5987

对，意思差不多。我记得那个做法没有用quicksort，是类似于二分？

【在 c********t 的大作中提到】

: quicksort? 与求kth in two sorted array 一样吧？

l*****a
发帖数: 14598

这题没法简化
数组长度不一
长度奇偶不定
边界点很难确定的
思路倒是简单，就是两分，然后每次抛掉肯定用不到的部分

【在 b***m 的大作中提到】

: 我记得上次有人发过一个很好的代码，但是我找不到了，貌似是C++递归实现的，代码
: 很短，应该只有十几行，没有用min-heap的。

f*****e
发帖数: 2992

用短array的median去分离长的，然后recurse。

【在 b***m 的大作中提到】

: 我记得上次有人发过一个很好的代码，但是我找不到了，貌似是C++递归实现的，代码
: 很短，应该只有十几行，没有用min-heap的。

相关主题
● find the k-th maximum node in a binary search tree 有疑问
● C++ Q23: if if else
● 问道Google题目
● 一道小题
进入JobHunting版参与讨论

b***m
发帖数: 5987

取两个数组各自的median，比较大小，然后把小的左边抛弃，大的右边抛弃，再继续取
median，如此反复？

【在 l*****a 的大作中提到】

: 这题没法简化
: 数组长度不一
: 长度奇偶不定
: 边界点很难确定的
: 思路倒是简单，就是两分，然后每次抛掉肯定用不到的部分

b***m
发帖数: 5987

什么叫做分离长的？

【在 f*****e 的大作中提到】

: 用短array的median去分离长的，然后recurse。

f*****e
发帖数: 2992

:
: 什么叫做分离长的？

b***m
发帖数: 5987

找到之后呢？

【在 f*****e 的大作中提到】

: 给定两个arrays，有一个长，有一个短，然后
: 就是找短array的median在长array中的位置啊，耗时O(lg(size of long array))。
: 然后继续recurse。

l*****a
发帖数: 14598

大的右边似乎只抛掉小的左边那么长，保证对称。。
基本就这个思路

【在 b***m 的大作中提到】

:
: 找到之后呢？

O******i
发帖数: 269

: 我记得上次有人发过一个很好的代码，但是我找不到了，貌似是C++递归实现的，代码
: 很短，应该只有十几行，没有用min-heap的。

f*****e
发帖数: 2992

然后就继续recurse，新的arrays长短就不一定了。

【在 b***m 的大作中提到】

:
: 找到之后呢？

b***m
发帖数: 5987

哦，对，好像貌似是这么个意思，我有点儿印象了……

【在 l*****a 的大作中提到】

: 大的右边似乎只抛掉小的左边那么长，保证对称。。
: 基本就这个思路

b***m
发帖数: 5987

做着玩玩嘛，反正最近闲着也是闲着。面SDET1问这种题确实是吃饱了撑的。

【在 O******i 的大作中提到】

C***U
发帖数: 2406

:
: 做着玩玩嘛，反正最近闲着也是闲着。面SDET1问这种题确实是吃饱了撑的。

相关主题
● Find Median Of Two Sorted Arrays
● 求两个有序数组的median的平凡解法?
● 请帖个Median of Two Sorted Arrays的好解法？
● 贡献一个Median of two sorted arrays的java code
进入JobHunting版参与讨论

O******i
发帖数: 269

其实先考虑两个数组等长的特殊情况，那个的递归log(N)解法比较好懂。
不等长就更难些。

【在 b***m 的大作中提到】

:
: 做着玩玩嘛，反正最近闲着也是闲着。面SDET1问这种题确实是吃饱了撑的。

b***m
发帖数: 5987

嗯，对，就是它，这个要收藏。

【在 C***U 的大作中提到】

O******i
发帖数: 269

华丽丽的先提升到一般解法(求kth)，进而轻松推出特殊解(k=中数)
问这题的面官肯定一看就知道是见过题的

【在 b***m 的大作中提到】

:
: 嗯，对，就是它，这个要收藏。

b***m
发帖数: 5987

真要用通用解法做这题就是给自己找麻烦，坛上某人已经吃过亏了。

【在 O******i 的大作中提到】

: 华丽丽的先提升到一般解法(求kth)，进而轻松推出特殊解(k=中数)
: 问这题的面官肯定一看就知道是见过题的

O******i
发帖数: 269

再问这题我就说见过，知道华丽解法，请君换题。

【在 b***m 的大作中提到】

:
: 真要用通用解法做这题就是给自己找麻烦，坛上某人已经吃过亏了。

l*******b
发帖数: 2586

O******i
发帖数: 269

其实就是O(m+n)的解法，也不容易bug free, 小心数组越界。

k-

【在 l*******b 的大作中提到】

l*******b
发帖数: 2586

嗯，想法其实挺直观的，在一个数组里做binary search，不过类似binary search的好
像都挺难bug free的

【在 O******i 的大作中提到】

: 其实就是O(m+n)的解法，也不容易bug free, 小心数组越界。
:
: k-

O******i
发帖数: 269

:
: 真要用通用解法做这题就是给自己找麻烦，坛上某人已经吃过亏了。

b***m
发帖数: 5987

试着写了一下，还真不好写，边界条件比较多。

相关主题
● 贡献一个Median of two sorted arrays的java code
● 百思不得其解的一道题目
● 跪了，Median of Two Sorted Arrays 问题求解
● 这个题目的比较好的方法是什么？
进入JobHunting版参与讨论

r****m
发帖数: 70

twitter电面被这道题搞挂

h****n
发帖数: 1093

你刚刚收藏的那个解法就是用通用解法来搞的
谁能贴一个不通过kth那个函数直接搞的log(m)+log(n)的简洁代码？

【在 b***m 的大作中提到】

: 试着写了一下，还真不好写，边界条件比较多。

Q*******e
发帖数: 939

这种问题如果没有见过,仔细想一下
当场就能写出bug free优化算法的, 算面试战斗机了.

l*******b
发帖数: 2586

偶数的时候有４种情况low_median和high_median分别在A或者Ｂ中。verify这个就得多
写好几句。感觉

【在 h****n 的大作中提到】

: 你刚刚收藏的那个解法就是用通用解法来搞的
: 谁能贴一个不通过kth那个函数直接搞的log(m)+log(n)的简洁代码？

l*******b
发帖数: 2586

最近翻的两本算法书上这个都是习题。应该算标准知识了

【在 Q*******e 的大作中提到】

: 这种问题如果没有见过,仔细想一下
: 当场就能写出bug free优化算法的, 算面试战斗机了.

c*****a
发帖数: 808

有java版吗....

【在 C***U 的大作中提到】

c**s
发帖数: 159

e******o
发帖数: 757

这个kth的要比找median 的容易写。median 还要考虑个数是奇数偶数之类的

【在 O******i 的大作中提到】

: 华丽丽的先提升到一般解法(求kth)，进而轻松推出特殊解(k=中数)
: 问这题的面官肯定一看就知道是见过题的

b***m
发帖数: 5987

对，是哦，我试着写了一下，思想虽然懂，代码还挺麻烦的。

【在 e******o 的大作中提到】

: 这个kth的要比找median 的容易写。median 还要考虑个数是奇数偶数之类的

相关主题
● Median of Two Sorted Arrays
● 为什么我的这个dynamic解法有错误
● 问道小学题：两等长有序数组，求第k个数
● 问道算法题
进入JobHunting版参与讨论

h**********w
发帖数: 39

牛解法，收藏了
public double findMedianSortedArrays(int A[], int B[]) {
int total = A.length+B.length;
if(total%2==1)
return recur(A,0,B,0,total/2+1);
else
return (recur(A,0,B,0, total/2)+recur(A,0,B,0,total/2+1))/2;

}

public double recur(int A[], int a, int B[], int b, int k){
int m = A.length-a;
int n = B.length-b;
if(m>n) return recur(B,b,A,a,k);
if(m==0) return B[k-1+b];
if(k==1) return Math.min(A[a], B[b]);
int pa = Math.min(k/2, m);
int pb = k - pa;

if(A[a+pa-1] return recur(A, a+pa, B,b,k-pa);
else
return recur(A, a, B,b+pb,k-pb);
}

【在 c*****a 的大作中提到】

:
: 有java版吗....

c****7
发帖数: 4192

找第k个，再找k+1个
public class Solution {
public double findMedianSortedArrays(int A[], int B[]) {
int l = A.length + B.length;
if (l % 2 == 0) {
return (find(A, 0, A.length, B, 0, B.length, l / 2) + find(A, 0,
A.length, B, 0, B.length, l / 2 - 1)) / 2.0;
} else {
return find(A, 0, A.length, B, 0, B.length, l / 2);
}
}
// k = 0 means the first element
public int find(int A[], int as, int ae, int B[], int bs, int be, int k)
{
if (as >= ae)
return B[bs + k];
if (bs >= be)
return A[as + k];
int am = (as + ae) / 2;
int bm = (bs + be) / 2;
//number of half elements including the middle elements
int h = am - as + bm - bs + 2;
if (A[am] < B[bm]) {
if (h > k + 1)
return find(A, as, ae, B, bs, bm, k);
else
return find(A, am + 1, ae, B, bs, be, k - (am - as + 1));
} else {
if (h > k + 1)
return find(A, as, am, B, bs, be, k);
else
return find(A, as, ae, B, bm + 1, be, k - (bm - bs + 1));
}
}
}

【在 b***m 的大作中提到】

: 我记得上次有人发过一个很好的代码，但是我找不到了，貌似是C++递归实现的，代码
: 很短，应该只有十几行，没有用min-heap的。

f*********d
发帖数: 140

//上一个我见过的最精简的代码吧，实战慎用:)
//注：非原创~
double findMedianSortedArrays(int A[], int m, int B[], int n)
{
if(m > n)
return findMedianSortedArrays(B, n, A, m);

int k = (n + m - 1) / 2;
int l = 0, r = m;
while (l < r) {
int mid = l + (r - l) / 2;
int bIdx = k - mid;
if (A[mid] < B[bIdx])
l = mid + 1;
else
r = mid;
}

int a = l - 1 >= 0 ? A[l - 1] : INT_MIN;
int b = k - l >= 0 ? B[k - l] : INT_MIN;
a = a >= b ? a : b;
if( (n + m) % 2 == 1) return a;
int c = k - l + 1 >= n ? INT_MAX : B[k - l + 1];
int d = l >= m ? INT_MAX: A[l];
c = c <= d ? c : d;
return ((double) (a + c)) / 2.0;
}

f********4
发帖数: 988

算法期中考试题~~

B********t
发帖数: 147

这题我写过一个1米长的。。就不贴了。。

(共1页)

进入JobHunting版参与讨论

相关主题
● 问道小学题：两等长有序数组，求第k个数
● 问道算法题
● median of two sorted arrays的时间复杂度(附上了过了oj的代码）
● find median for k sorted arrays
● 问一道google的题
● 找第K个最小的元素
● find the k-th maximum node in a binary search tree 有疑问
● C++ Q23: if if else
● 问道Google题目
● 一道小题

相关话题的讨论汇总
话题: int话题: return话题: mid话题: else话题: double

boards