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 偶数的时候有４种情况low_median和high_median分别在A或者Ｂ中。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 偶数的时候有４种情况low_median和high_median分别在A或者Ｂ中。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 | |
|
