b***m 发帖数: 5987 | 1 我记得上次有人发过一个很好的代码,但是我找不到了,貌似是C++递归实现的,代码
很短,应该只有十几行,没有用min-heap的。 | c********t 发帖数: 5706 | 2 quicksort? 与求kth in two sorted array 一样吧?
【在 b***m 的大作中提到】 : 我记得上次有人发过一个很好的代码,但是我找不到了,貌似是C++递归实现的,代码 : 很短,应该只有十几行,没有用min-heap的。
| b***m 发帖数: 5987 | 3
对,意思差不多。我记得那个做法没有用quicksort,是类似于二分?
【在 c********t 的大作中提到】 : quicksort? 与求kth in two sorted array 一样吧?
| l*****a 发帖数: 14598 | 4 这题没法简化
数组长度不一
长度奇偶不定
边界点很难确定的
思路倒是简单,就是两分,然后每次抛掉肯定用不到的部分
【在 b***m 的大作中提到】 : 我记得上次有人发过一个很好的代码,但是我找不到了,貌似是C++递归实现的,代码 : 很短,应该只有十几行,没有用min-heap的。
| f*****e 发帖数: 2992 | 5 用短array的median去分离长的,然后recurse。
【在 b***m 的大作中提到】 : 我记得上次有人发过一个很好的代码,但是我找不到了,貌似是C++递归实现的,代码 : 很短,应该只有十几行,没有用min-heap的。
| b***m 发帖数: 5987 | 6
取两个数组各自的median,比较大小,然后把小的左边抛弃,大的右边抛弃,再继续取
median,如此反复?
【在 l*****a 的大作中提到】 : 这题没法简化 : 数组长度不一 : 长度奇偶不定 : 边界点很难确定的 : 思路倒是简单,就是两分,然后每次抛掉肯定用不到的部分
| b***m 发帖数: 5987 | 7
什么叫做分离长的?
【在 f*****e 的大作中提到】 : 用短array的median去分离长的,然后recurse。
| f*****e 发帖数: 2992 | 8 给定两个arrays,有一个长,有一个短,然后
就是找短array的median在长array中的位置啊,耗时O(lg(size of long array))。
然后继续recurse。
【在 b***m 的大作中提到】 : : 什么叫做分离长的?
| b***m 发帖数: 5987 | 9
找到之后呢?
【在 f*****e 的大作中提到】 : 给定两个arrays,有一个长,有一个短,然后 : 就是找短array的median在长array中的位置啊,耗时O(lg(size of long array))。 : 然后继续recurse。
| l*****a 发帖数: 14598 | 10 大的右边似乎只抛掉小的左边那么长,保证对称。。
基本就这个思路
【在 b***m 的大作中提到】 : : 找到之后呢?
| | | O******i 发帖数: 269 | 11 都拿到大卧佛了还子孜孜不倦做题啊?
这题从来没看过是很难想到log(N)的解法的,我第一次面M的SDET的时候陪吃午饭的阿
三就问的,尼玛,SDET1至于要问这么难的题么?
【在 b***m 的大作中提到】 : 我记得上次有人发过一个很好的代码,但是我找不到了,貌似是C++递归实现的,代码 : 很短,应该只有十几行,没有用min-heap的。
| f*****e 发帖数: 2992 | 12 然后就继续recurse,新的arrays长短就不一定了。
【在 b***m 的大作中提到】 : : 找到之后呢?
| b***m 发帖数: 5987 | 13
哦,对,好像貌似是这么个意思,我有点儿印象了……
【在 l*****a 的大作中提到】 : 大的右边似乎只抛掉小的左边那么长,保证对称。。 : 基本就这个思路
| b***m 发帖数: 5987 | 14
做着玩玩嘛,反正最近闲着也是闲着。面SDET1问这种题确实是吃饱了撑的。
【在 O******i 的大作中提到】 : 都拿到大卧佛了还子孜孜不倦做题啊? : 这题从来没看过是很难想到log(N)的解法的,我第一次面M的SDET的时候陪吃午饭的阿 : 三就问的,尼玛,SDET1至于要问这么难的题么?
| C***U 发帖数: 2406 | 15 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 | 16 其实先考虑两个数组等长的特殊情况,那个的递归log(N)解法比较好懂。
不等长就更难些。
【在 b***m 的大作中提到】 : : 做着玩玩嘛,反正最近闲着也是闲着。面SDET1问这种题确实是吃饱了撑的。
| b***m 发帖数: 5987 | 17
嗯,对,就是它,这个要收藏。
【在 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 | 18 华丽丽的先提升到一般解法(求kth),进而轻松推出特殊解(k=中数)
问这题的面官肯定一看就知道是见过题的
【在 b***m 的大作中提到】 : : 嗯,对,就是它,这个要收藏。
| b***m 发帖数: 5987 | 19
真要用通用解法做这题就是给自己找麻烦,坛上某人已经吃过亏了。
【在 O******i 的大作中提到】 : 华丽丽的先提升到一般解法(求kth),进而轻松推出特殊解(k=中数) : 问这题的面官肯定一看就知道是见过题的
| O******i 发帖数: 269 | 20 再问这题我就说见过,知道华丽解法,请君换题。
【在 b***m 的大作中提到】 : : 真要用通用解法做这题就是给自己找麻烦,坛上某人已经吃过亏了。
| | | l*******b 发帖数: 2586 | 21 这个递归写得好简洁呀。。。贴个自己写的,这题总觉得边界情况太复杂
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 | 22 其实就是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 | 23 嗯,想法其实挺直观的,在一个数组里做binary search,不过类似binary search的好
像都挺难bug free的
【在 O******i 的大作中提到】 : 其实就是O(m+n)的解法,也不容易bug free, 小心数组越界。 : : k-
| O******i 发帖数: 269 | 24 阿三可能就想看一个O(m+n)的简单解法,不过就那样我当时也没有写好,下标有越界
。我是后来才知道有O(log(m+n))的解法,这题好像是CLRS的课后习题。
【在 b***m 的大作中提到】 : : 真要用通用解法做这题就是给自己找麻烦,坛上某人已经吃过亏了。
| b***m 发帖数: 5987 | | r****m 发帖数: 70 | | h****n 发帖数: 1093 | 27 你刚刚收藏的那个解法就是用通用解法来搞的
谁能贴一个不通过kth那个函数直接搞的log(m)+log(n)的简洁代码?
【在 b***m 的大作中提到】 : 试着写了一下,还真不好写,边界条件比较多。
| Q*******e 发帖数: 939 | 28 这种问题如果没有见过,仔细想一下
当场就能写出bug free优化算法的, 算面试战斗机了. | l*******b 发帖数: 2586 | 29 偶数的时候有4种情况low_median和high_median分别在A或者B中。verify这个就得多
写好几句。感觉
【在 h****n 的大作中提到】 : 你刚刚收藏的那个解法就是用通用解法来搞的 : 谁能贴一个不通过kth那个函数直接搞的log(m)+log(n)的简洁代码?
| l*******b 发帖数: 2586 | 30 最近翻的两本算法书上这个都是习题。应该算标准知识了
【在 Q*******e 的大作中提到】 : 这种问题如果没有见过,仔细想一下 : 当场就能写出bug free优化算法的, 算面试战斗机了.
| | | c*****a 发帖数: 808 | 31 我的不简洁了.....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 | 32
有java版吗....
【在 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
| c**s 发帖数: 159 | 33 贴一个我写的:
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 | 34 这个kth的要比找median 的容易写。median 还要考虑个数是奇数偶数之类的
【在 O******i 的大作中提到】 : 华丽丽的先提升到一般解法(求kth),进而轻松推出特殊解(k=中数) : 问这题的面官肯定一看就知道是见过题的
| b***m 发帖数: 5987 | 35 对,是哦,我试着写了一下,思想虽然懂,代码还挺麻烦的。
【在 e******o 的大作中提到】 : 这个kth的要比找median 的容易写。median 还要考虑个数是奇数偶数之类的
| b***m 发帖数: 5987 | 36 我记得上次有人发过一个很好的代码,但是我找不到了,貌似是C++递归实现的,代码
很短,应该只有十几行,没有用min-heap的。 | c********t 发帖数: 5706 | 37 quicksort? 与求kth in two sorted array 一样吧?
【在 b***m 的大作中提到】 : 我记得上次有人发过一个很好的代码,但是我找不到了,貌似是C++递归实现的,代码 : 很短,应该只有十几行,没有用min-heap的。
| b***m 发帖数: 5987 | 38
对,意思差不多。我记得那个做法没有用quicksort,是类似于二分?
【在 c********t 的大作中提到】 : quicksort? 与求kth in two sorted array 一样吧?
| l*****a 发帖数: 14598 | 39 这题没法简化
数组长度不一
长度奇偶不定
边界点很难确定的
思路倒是简单,就是两分,然后每次抛掉肯定用不到的部分
【在 b***m 的大作中提到】 : 我记得上次有人发过一个很好的代码,但是我找不到了,貌似是C++递归实现的,代码 : 很短,应该只有十几行,没有用min-heap的。
| f*****e 发帖数: 2992 | 40 用短array的median去分离长的,然后recurse。
【在 b***m 的大作中提到】 : 我记得上次有人发过一个很好的代码,但是我找不到了,貌似是C++递归实现的,代码 : 很短,应该只有十几行,没有用min-heap的。
| | | b***m 发帖数: 5987 | 41
取两个数组各自的median,比较大小,然后把小的左边抛弃,大的右边抛弃,再继续取
median,如此反复?
【在 l*****a 的大作中提到】 : 这题没法简化 : 数组长度不一 : 长度奇偶不定 : 边界点很难确定的 : 思路倒是简单,就是两分,然后每次抛掉肯定用不到的部分
| b***m 发帖数: 5987 | 42
什么叫做分离长的?
【在 f*****e 的大作中提到】 : 用短array的median去分离长的,然后recurse。
| f*****e 发帖数: 2992 | 43 给定两个arrays,有一个长,有一个短,然后
就是找短array的median在长array中的位置啊,耗时O(lg(size of long array))。
然后继续recurse。
【在 b***m 的大作中提到】 : : 什么叫做分离长的?
| b***m 发帖数: 5987 | 44
找到之后呢?
【在 f*****e 的大作中提到】 : 给定两个arrays,有一个长,有一个短,然后 : 就是找短array的median在长array中的位置啊,耗时O(lg(size of long array))。 : 然后继续recurse。
| l*****a 发帖数: 14598 | 45 大的右边似乎只抛掉小的左边那么长,保证对称。。
基本就这个思路
【在 b***m 的大作中提到】 : : 找到之后呢?
| O******i 发帖数: 269 | 46 都拿到大卧佛了还子孜孜不倦做题啊?
这题从来没看过是很难想到log(N)的解法的,我第一次面M的SDET的时候陪吃午饭的阿
三就问的,尼玛,SDET1至于要问这么难的题么?
【在 b***m 的大作中提到】 : 我记得上次有人发过一个很好的代码,但是我找不到了,貌似是C++递归实现的,代码 : 很短,应该只有十几行,没有用min-heap的。
| f*****e 发帖数: 2992 | 47 然后就继续recurse,新的arrays长短就不一定了。
【在 b***m 的大作中提到】 : : 找到之后呢?
| b***m 发帖数: 5987 | 48
哦,对,好像貌似是这么个意思,我有点儿印象了……
【在 l*****a 的大作中提到】 : 大的右边似乎只抛掉小的左边那么长,保证对称。。 : 基本就这个思路
| b***m 发帖数: 5987 | 49
做着玩玩嘛,反正最近闲着也是闲着。面SDET1问这种题确实是吃饱了撑的。
【在 O******i 的大作中提到】 : 都拿到大卧佛了还子孜孜不倦做题啊? : 这题从来没看过是很难想到log(N)的解法的,我第一次面M的SDET的时候陪吃午饭的阿 : 三就问的,尼玛,SDET1至于要问这么难的题么?
| C***U 发帖数: 2406 | 50 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 | 51 其实先考虑两个数组等长的特殊情况,那个的递归log(N)解法比较好懂。
不等长就更难些。
【在 b***m 的大作中提到】 : : 做着玩玩嘛,反正最近闲着也是闲着。面SDET1问这种题确实是吃饱了撑的。
| b***m 发帖数: 5987 | 52
嗯,对,就是它,这个要收藏。
【在 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 | 53 华丽丽的先提升到一般解法(求kth),进而轻松推出特殊解(k=中数)
问这题的面官肯定一看就知道是见过题的
【在 b***m 的大作中提到】 : : 嗯,对,就是它,这个要收藏。
| b***m 发帖数: 5987 | 54
真要用通用解法做这题就是给自己找麻烦,坛上某人已经吃过亏了。
【在 O******i 的大作中提到】 : 华丽丽的先提升到一般解法(求kth),进而轻松推出特殊解(k=中数) : 问这题的面官肯定一看就知道是见过题的
| O******i 发帖数: 269 | 55 再问这题我就说见过,知道华丽解法,请君换题。
【在 b***m 的大作中提到】 : : 真要用通用解法做这题就是给自己找麻烦,坛上某人已经吃过亏了。
| l*******b 发帖数: 2586 | 56 这个递归写得好简洁呀。。。贴个自己写的,这题总觉得边界情况太复杂
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 | 57 其实就是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 | 58 嗯,想法其实挺直观的,在一个数组里做binary search,不过类似binary search的好
像都挺难bug free的
【在 O******i 的大作中提到】 : 其实就是O(m+n)的解法,也不容易bug free, 小心数组越界。 : : k-
| O******i 发帖数: 269 | 59 阿三可能就想看一个O(m+n)的简单解法,不过就那样我当时也没有写好,下标有越界
。我是后来才知道有O(log(m+n))的解法,这题好像是CLRS的课后习题。
【在 b***m 的大作中提到】 : : 真要用通用解法做这题就是给自己找麻烦,坛上某人已经吃过亏了。
| b***m 发帖数: 5987 | | | | r****m 发帖数: 70 | | h****n 发帖数: 1093 | 62 你刚刚收藏的那个解法就是用通用解法来搞的
谁能贴一个不通过kth那个函数直接搞的log(m)+log(n)的简洁代码?
【在 b***m 的大作中提到】 : 试着写了一下,还真不好写,边界条件比较多。
| Q*******e 发帖数: 939 | 63 这种问题如果没有见过,仔细想一下
当场就能写出bug free优化算法的, 算面试战斗机了. | l*******b 发帖数: 2586 | 64 偶数的时候有4种情况low_median和high_median分别在A或者B中。verify这个就得多
写好几句。感觉
【在 h****n 的大作中提到】 : 你刚刚收藏的那个解法就是用通用解法来搞的 : 谁能贴一个不通过kth那个函数直接搞的log(m)+log(n)的简洁代码?
| l*******b 发帖数: 2586 | 65 最近翻的两本算法书上这个都是习题。应该算标准知识了
【在 Q*******e 的大作中提到】 : 这种问题如果没有见过,仔细想一下 : 当场就能写出bug free优化算法的, 算面试战斗机了.
| c*****a 发帖数: 808 | 66 我的不简洁了.....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 | 67
有java版吗....
【在 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
| c**s 发帖数: 159 | 68 贴一个我写的:
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 | 69 这个kth的要比找median 的容易写。median 还要考虑个数是奇数偶数之类的
【在 O******i 的大作中提到】 : 华丽丽的先提升到一般解法(求kth),进而轻松推出特殊解(k=中数) : 问这题的面官肯定一看就知道是见过题的
| b***m 发帖数: 5987 | 70 对,是哦,我试着写了一下,思想虽然懂,代码还挺麻烦的。
【在 e******o 的大作中提到】 : 这个kth的要比找median 的容易写。median 还要考虑个数是奇数偶数之类的
| | | h**********w 发帖数: 39 | 71 牛解法,收藏了
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 | 72 找第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 | 73 //上一个我见过的最精简的代码吧,实战慎用:)
//注: 非原创~
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 | |
|