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