Redian新闻
>
都这时候了,店里的菜苗也不降价
avatar
都这时候了,店里的菜苗也不降价# gardening - 拈花惹草
b*m
1
我记得上次有人发过一个很好的代码,但是我找不到了,貌似是C++递归实现的,代码
很短,应该只有十几行,没有用min-heap的。
avatar
e*0
2
想补种几颗西红柿辣椒啥的,店里一看居然还是原价,只好悻悻然买了几颗。
avatar
c*t
3
quicksort? 与求kth in two sorted array 一样吧?

【在 b***m 的大作中提到】
: 我记得上次有人发过一个很好的代码,但是我找不到了,貌似是C++递归实现的,代码
: 很短,应该只有十几行,没有用min-heap的。

avatar
o*n
4
店家等你很久了 lol
菜苗放到现在的机会成本很高,一直照顾人工成本高
avatar
b*m
5

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

【在 c********t 的大作中提到】
: quicksort? 与求kth in two sorted array 一样吧?
avatar
s*u
6
现在收刮一个算一个咯。

【在 o*******n 的大作中提到】
: 店家等你很久了 lol
: 菜苗放到现在的机会成本很高,一直照顾人工成本高

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

【在 b***m 的大作中提到】
: 我记得上次有人发过一个很好的代码,但是我找不到了,貌似是C++递归实现的,代码
: 很短,应该只有十几行,没有用min-heap的。

avatar
o*i
8
如今经济好。。。打折的就少了
avatar
f*e
9
用短array的median去分离长的,然后recurse。

【在 b***m 的大作中提到】
: 我记得上次有人发过一个很好的代码,但是我找不到了,貌似是C++递归实现的,代码
: 很短,应该只有十几行,没有用min-heap的。

avatar
b*m
10

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

【在 l*****a 的大作中提到】
: 这题没法简化
: 数组长度不一
: 长度奇偶不定
: 边界点很难确定的
: 思路倒是简单,就是两分,然后每次抛掉肯定用不到的部分

avatar
b*m
11

什么叫做分离长的?

【在 f*****e 的大作中提到】
: 用短array的median去分离长的,然后recurse。
avatar
f*e
12
给定两个arrays,有一个长,有一个短,然后
就是找短array的median在长array中的位置啊,耗时O(lg(size of long array))。
然后继续recurse。

【在 b***m 的大作中提到】
:
: 什么叫做分离长的?

avatar
b*m
13

找到之后呢?

【在 f*****e 的大作中提到】
: 给定两个arrays,有一个长,有一个短,然后
: 就是找短array的median在长array中的位置啊,耗时O(lg(size of long array))。
: 然后继续recurse。

avatar
l*a
14
大的右边似乎只抛掉小的左边那么长,保证对称。。
基本就这个思路

【在 b***m 的大作中提到】
:
: 找到之后呢?

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

【在 b***m 的大作中提到】
: 我记得上次有人发过一个很好的代码,但是我找不到了,貌似是C++递归实现的,代码
: 很短,应该只有十几行,没有用min-heap的。

avatar
f*e
16
然后就继续recurse,新的arrays长短就不一定了。

【在 b***m 的大作中提到】
:
: 找到之后呢?

avatar
b*m
17

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

【在 l*****a 的大作中提到】
: 大的右边似乎只抛掉小的左边那么长,保证对称。。
: 基本就这个思路

avatar
b*m
18

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

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

avatar
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问这种题确实是吃饱了撑的。

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

【在 b***m 的大作中提到】
:
: 做着玩玩嘛,反正最近闲着也是闲着。面SDET1问这种题确实是吃饱了撑的。

avatar
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

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

【在 b***m 的大作中提到】
:
: 嗯,对,就是它,这个要收藏。

avatar
b*m
23

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

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

avatar
O*i
24
再问这题我就说见过,知道华丽解法,请君换题。

【在 b***m 的大作中提到】
:
: 真要用通用解法做这题就是给自己找麻烦,坛上某人已经吃过亏了。

avatar
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;
}
avatar
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;

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

【在 O******i 的大作中提到】
: 其实就是O(m+n)的解法,也不容易bug free, 小心数组越界。
:
: k-

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

【在 b***m 的大作中提到】
:
: 真要用通用解法做这题就是给自己找麻烦,坛上某人已经吃过亏了。

avatar
b*m
29
试着写了一下,还真不好写,边界条件比较多。
avatar
r*m
30
twitter电面被这道题搞挂
avatar
h*n
31
你刚刚收藏的那个解法就是用通用解法来搞的
谁能贴一个不通过kth那个函数直接搞的log(m)+log(n)的简洁代码?

【在 b***m 的大作中提到】
: 试着写了一下,还真不好写,边界条件比较多。
avatar
Q*e
32
这种问题如果没有见过,仔细想一下
当场就能写出bug free优化算法的, 算面试战斗机了.
avatar
l*b
33
偶数的时候有4种情况low_median和high_median分别在A或者B中。verify这个就得多
写好几句。感觉

【在 h****n 的大作中提到】
: 你刚刚收藏的那个解法就是用通用解法来搞的
: 谁能贴一个不通过kth那个函数直接搞的log(m)+log(n)的简洁代码?

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

【在 Q*******e 的大作中提到】
: 这种问题如果没有见过,仔细想一下
: 当场就能写出bug free优化算法的, 算面试战斗机了.

avatar
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];
}
}
}
avatar
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

avatar
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);

}
};
avatar
e*o
38
这个kth的要比找median 的容易写。median 还要考虑个数是奇数偶数之类的

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

avatar
b*m
39
对,是哦,我试着写了一下,思想虽然懂,代码还挺麻烦的。

【在 e******o 的大作中提到】
: 这个kth的要比找median 的容易写。median 还要考虑个数是奇数偶数之类的
avatar
b*m
40
我记得上次有人发过一个很好的代码,但是我找不到了,貌似是C++递归实现的,代码
很短,应该只有十几行,没有用min-heap的。
avatar
c*t
41
quicksort? 与求kth in two sorted array 一样吧?

【在 b***m 的大作中提到】
: 我记得上次有人发过一个很好的代码,但是我找不到了,貌似是C++递归实现的,代码
: 很短,应该只有十几行,没有用min-heap的。

avatar
b*m
42

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

【在 c********t 的大作中提到】
: quicksort? 与求kth in two sorted array 一样吧?
avatar
l*a
43
这题没法简化
数组长度不一
长度奇偶不定
边界点很难确定的
思路倒是简单,就是两分,然后每次抛掉肯定用不到的部分

【在 b***m 的大作中提到】
: 我记得上次有人发过一个很好的代码,但是我找不到了,貌似是C++递归实现的,代码
: 很短,应该只有十几行,没有用min-heap的。

avatar
f*e
44
用短array的median去分离长的,然后recurse。

【在 b***m 的大作中提到】
: 我记得上次有人发过一个很好的代码,但是我找不到了,貌似是C++递归实现的,代码
: 很短,应该只有十几行,没有用min-heap的。

avatar
b*m
45

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

【在 l*****a 的大作中提到】
: 这题没法简化
: 数组长度不一
: 长度奇偶不定
: 边界点很难确定的
: 思路倒是简单,就是两分,然后每次抛掉肯定用不到的部分

avatar
b*m
46

什么叫做分离长的?

【在 f*****e 的大作中提到】
: 用短array的median去分离长的,然后recurse。
avatar
f*e
47
给定两个arrays,有一个长,有一个短,然后
就是找短array的median在长array中的位置啊,耗时O(lg(size of long array))。
然后继续recurse。

【在 b***m 的大作中提到】
:
: 什么叫做分离长的?

avatar
b*m
48

找到之后呢?

【在 f*****e 的大作中提到】
: 给定两个arrays,有一个长,有一个短,然后
: 就是找短array的median在长array中的位置啊,耗时O(lg(size of long array))。
: 然后继续recurse。

avatar
l*a
49
大的右边似乎只抛掉小的左边那么长,保证对称。。
基本就这个思路

【在 b***m 的大作中提到】
:
: 找到之后呢?

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

【在 b***m 的大作中提到】
: 我记得上次有人发过一个很好的代码,但是我找不到了,貌似是C++递归实现的,代码
: 很短,应该只有十几行,没有用min-heap的。

avatar
f*e
51
然后就继续recurse,新的arrays长短就不一定了。

【在 b***m 的大作中提到】
:
: 找到之后呢?

avatar
b*m
52

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

【在 l*****a 的大作中提到】
: 大的右边似乎只抛掉小的左边那么长,保证对称。。
: 基本就这个思路

avatar
b*m
53

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

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

avatar
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问这种题确实是吃饱了撑的。

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

【在 b***m 的大作中提到】
:
: 做着玩玩嘛,反正最近闲着也是闲着。面SDET1问这种题确实是吃饱了撑的。

avatar
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

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

【在 b***m 的大作中提到】
:
: 嗯,对,就是它,这个要收藏。

avatar
b*m
58

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

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

avatar
O*i
59
再问这题我就说见过,知道华丽解法,请君换题。

【在 b***m 的大作中提到】
:
: 真要用通用解法做这题就是给自己找麻烦,坛上某人已经吃过亏了。

avatar
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;
}
avatar
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;

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

【在 O******i 的大作中提到】
: 其实就是O(m+n)的解法,也不容易bug free, 小心数组越界。
:
: k-

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

【在 b***m 的大作中提到】
:
: 真要用通用解法做这题就是给自己找麻烦,坛上某人已经吃过亏了。

avatar
b*m
64
试着写了一下,还真不好写,边界条件比较多。
avatar
r*m
65
twitter电面被这道题搞挂
avatar
h*n
66
你刚刚收藏的那个解法就是用通用解法来搞的
谁能贴一个不通过kth那个函数直接搞的log(m)+log(n)的简洁代码?

【在 b***m 的大作中提到】
: 试着写了一下,还真不好写,边界条件比较多。
avatar
Q*e
67
这种问题如果没有见过,仔细想一下
当场就能写出bug free优化算法的, 算面试战斗机了.
avatar
l*b
68
偶数的时候有4种情况low_median和high_median分别在A或者B中。verify这个就得多
写好几句。感觉

【在 h****n 的大作中提到】
: 你刚刚收藏的那个解法就是用通用解法来搞的
: 谁能贴一个不通过kth那个函数直接搞的log(m)+log(n)的简洁代码?

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

【在 Q*******e 的大作中提到】
: 这种问题如果没有见过,仔细想一下
: 当场就能写出bug free优化算法的, 算面试战斗机了.

avatar
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];
}
}
}
avatar
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

avatar
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);

}
};
avatar
e*o
73
这个kth的要比找median 的容易写。median 还要考虑个数是奇数偶数之类的

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

avatar
b*m
74
对,是哦,我试着写了一下,思想虽然懂,代码还挺麻烦的。

【在 e******o 的大作中提到】
: 这个kth的要比找median 的容易写。median 还要考虑个数是奇数偶数之类的
avatar
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版吗....

avatar
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的。

avatar
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;
}
avatar
f*4
78
算法期中考试题~~
avatar
B*t
79
这题我写过一个1米长的。。就不贴了。。
相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。