Redian新闻
>
求两个有序数组的median的平凡解法?
avatar
求两个有序数组的median的平凡解法?# JobHunting - 待字闺中
K*k
1
要求in place, 只要求O(m + n)的方法,不需要log(m + n)那个。我写的代码还是觉得太长,怎么简化才能在白板上写的下?
double GetMedian(int A[], int m, int B[], int n)
{
bool odd_length = ((m + n) % 2 == 0)? false : true;
int m1, m2;
int pos = (m + n + 1) / 2;
int count = 0;
int i = 0;
int j = 0;
while (i < m && j < n)
{
count++;

if (A[i] <= B[j])
{
if (count == pos)
{
m1 = A[i];
if (odd_length)
return m1;
}
else if (count == pos + 1)
{
m2 = A[i];
return (m1 + m2) / 2.0;
}
i++;
}
else
{
if (count == pos)
{
m1 = B[j];
if (odd_length)
return m1;
}
else if (count == pos + 1)
{
m2 = B[j];
return (m1 + m2) / 2.0;
}
j++;
}
}
while (i < m)
{
count++;
if (count == pos)
{
m1 = A[i];

if (odd_length)
return m1;
}
else if (count == pos + 1)
{
m2 = A[i];
return (m1 + m2) / 2.0;
}
i++;
}
while (j < n)
{
count++;
if (count == pos)
{
m1 = B[j];
if (odd_length)
return m1;
}
else if (count == pos + 1)
{
m2 = B[j];
return (m1 + m2) / 2.0;
}
j++;
}
return 0.0;
}
avatar
f*t
2
int median(int a[], int m, int b[], int n)
{
int target = (m + n) / 2; // Be careful for overflow
int indexA = 0, indexB = 0;
while(--target) {
if(indexA == m-1)
indexB++;
else if(indexB == n-1)
indexA++;
else if(a[indexA] < b[indexB])
indexA++;
else
indexB++;
}
if((m ^ n) & 1)
return min(a[indexA], b[indexB]);
else
return (a[indexA] + b[indexB]) / 2;
}
avatar
K*k
3
没看明白。
而且当总共的元素个数为偶数的时候,median的定义是中间两个数的平均数。
比如
int A[] = {1};
int B[] = {5, 6, 7, 8, 9};
合并后是{1, 5, 6, 7, 8, 9}, median = (6 + 7) / 2 = 6.5

【在 f*******t 的大作中提到】
: int median(int a[], int m, int b[], int n)
: {
: int target = (m + n) / 2; // Be careful for overflow
: int indexA = 0, indexB = 0;
: while(--target) {
: if(indexA == m-1)
: indexB++;
: else if(indexB == n-1)
: indexA++;
: else if(a[indexA] < b[indexB])

avatar
K*k
4
这道题在ihasleetcode的网站上有巧妙的log(m+n)的解法,但对面试来说太难。
有人onsite的时候被问过这题么?
avatar
f*t
5
要返回平均数的话改下最后的return语句就行。
最好的算法是logk的(找第k小的元素),其实不算难,我觉得面试考这题的机会还是挺多的,背好代
码就行。。。

【在 K*****k 的大作中提到】
: 没看明白。
: 而且当总共的元素个数为偶数的时候,median的定义是中间两个数的平均数。
: 比如
: int A[] = {1};
: int B[] = {5, 6, 7, 8, 9};
: 合并后是{1, 5, 6, 7, 8, 9}, median = (6 + 7) / 2 = 6.5

avatar
K*k
6
你原来的代码对test case
A[] = {1};
B[] = {5, 6, 7, 8, 9};
m = 1
n = 5
结果不对,好像return的时候去引用A[1], 越界了。能否检查一下。

是挺多的,背好代

【在 f*******t 的大作中提到】
: 要返回平均数的话改下最后的return语句就行。
: 最好的算法是logk的(找第k小的元素),其实不算难,我觉得面试考这题的机会还是挺多的,背好代
: 码就行。。。

avatar
k*n
7
我被问过,当时就毛了,最后歇比了
算法上根本没啥难的,各种小细节小边界条件,坑死爹阿
以后见到老印就拿这个问,定了

【在 K*****k 的大作中提到】
: 这道题在ihasleetcode的网站上有巧妙的log(m+n)的解法,但对面试来说太难。
: 有人onsite的时候被问过这题么?

avatar
f*t
8
嗯,确实有bug
在原楼编辑了

【在 K*****k 的大作中提到】
: 你原来的代码对test case
: A[] = {1};
: B[] = {5, 6, 7, 8, 9};
: m = 1
: n = 5
: 结果不对,好像return的时候去引用A[1], 越界了。能否检查一下。
:
: 是挺多的,背好代

avatar
B*1
9
1337那个帖子下面有个读者给出的也是最优化的,1337也肯定了那个人的code,而且写
得很简单,就是改mit的解法出来的。
1337那个写得太复杂了。

【在 k****n 的大作中提到】
: 我被问过,当时就毛了,最后歇比了
: 算法上根本没啥难的,各种小细节小边界条件,坑死爹阿
: 以后见到老印就拿这个问,定了

avatar
K*k
10
那个log(m + n)的算法现场想到还是很难的,好像MIT某个课程的handout中有解答,但
对偶数个元素,也是求出第一个median, 而不是两个median的平均值。
ihasleetcode的网站有完整巧妙的几种解答方法,可惜我觉得对于面试的白板来说,可
用空间太小了,写不下。

【在 k****n 的大作中提到】
: 我被问过,当时就毛了,最后歇比了
: 算法上根本没啥难的,各种小细节小边界条件,坑死爹阿
: 以后见到老印就拿这个问,定了

avatar
H*M
11
跟merge sort比较象,往前爬,同事记住爬的数目,等总共爬了一半,就是中树的附近
?不过边界条件要整一整

得太长,怎么简化才能在白板上写的下?

【在 K*****k 的大作中提到】
: 要求in place, 只要求O(m + n)的方法,不需要log(m + n)那个。我写的代码还是觉得太长,怎么简化才能在白板上写的下?
: double GetMedian(int A[], int m, int B[], int n)
: {
: bool odd_length = ((m + n) % 2 == 0)? false : true;
: int m1, m2;
: int pos = (m + n + 1) / 2;
: int count = 0;
: int i = 0;
: int j = 0;
: while (i < m && j < n)

avatar
f*t
12
lgk查找递归方法不长的,我顺便发个收藏的代码吧。记不得作者是谁……
int findKthFrom2SortedArraysIterative(int *arr1, int *arr2, int k){
int result;
int mid;
int curPosOfArr1 = 0, curPosOfArr2 = 0;
while(k > 1){
mid = k/2;
if(arr1[curPosOfArr1 + mid - 1] < arr2[curPosOfArr2 + mid - 1]){

curPosOfArr1 = curPosOfArr1 + mid;
}else{
curPosOfArr2 = curPosOfArr2 + mid;
}
k = k - mid;
}
if(arr1[curPosOfArr1] > arr2[curPosOfArr2]){
return arr2[curPosOfArr2];
}else{
return arr1[curPosOfArr1];
}

return result;
}
int findKthFrom2SortedArraysRecursion(int *arr1, int *arr2, int k, int
arr1Index, int arr2Index){
if(k == 1){
if(arr1[arr1Index] <= arr2[arr2Index])
return arr1[arr1Index];
else
return arr2[arr2Index];
}
int curPos = k/2;
if(arr1[arr1Index + curPos - 1] <= arr2[arr2Index + curPos - 1])
findKthFrom2SortedArraysRecursion(arr1, arr2, k - curPos, arr1Index
+ curPos, arr2Index);
else
findKthFrom2SortedArraysRecursion(arr1, arr2, k - curPos, arr1Index,
arr2Index + curPos);
}
avatar
b*g
13
大概的还不错。
A[] = {1};
B[] = {5, 6, 7, 8, 9};
m = 1
n = 5
用楼上的例子,你的算法要越界啊,是针对第一个数组arr1在第二次循环的时候。



【在 f*******t 的大作中提到】
: lgk查找递归方法不长的,我顺便发个收藏的代码吧。记不得作者是谁……
: int findKthFrom2SortedArraysIterative(int *arr1, int *arr2, int k){
: int result;
: int mid;
: int curPosOfArr1 = 0, curPosOfArr2 = 0;
: while(k > 1){
: mid = k/2;
: if(arr1[curPosOfArr1 + mid - 1] < arr2[curPosOfArr2 + mid - 1]){
:
: curPosOfArr1 = curPosOfArr1 + mid;

avatar
b*g
14
这个挺好的,不过
最后(m ^ n) & 1 能不能改成 (m==n)啊,要不然太耍深奥了吧。

【在 f*******t 的大作中提到】
: int median(int a[], int m, int b[], int n)
: {
: int target = (m + n) / 2; // Be careful for overflow
: int indexA = 0, indexB = 0;
: while(--target) {
: if(indexA == m-1)
: indexB++;
: else if(indexB == n-1)
: indexA++;
: else if(a[indexA] < b[indexB])

avatar
A*u
15
这玩意太复杂了

得太长,怎么简化才能在白板上写的下?

【在 K*****k 的大作中提到】
: 要求in place, 只要求O(m + n)的方法,不需要log(m + n)那个。我写的代码还是觉得太长,怎么简化才能在白板上写的下?
: double GetMedian(int A[], int m, int B[], int n)
: {
: bool odd_length = ((m + n) % 2 == 0)? false : true;
: int m1, m2;
: int pos = (m + n + 1) / 2;
: int count = 0;
: int i = 0;
: int j = 0;
: while (i < m && j < n)

avatar
f*t
16
这句是用来判断m+n的奇偶性……

【在 b******g 的大作中提到】
: 这个挺好的,不过
: 最后(m ^ n) & 1 能不能改成 (m==n)啊,要不然太耍深奥了吧。

avatar
w*p
17
请教您指的ihasleetcode是http://www.leetcode.com/ 还是http://www.weiming.info/author/ihasleetcode/ 或是其他?
谢谢。
有包子送的哦!

【在 K*****k 的大作中提到】
: 这道题在ihasleetcode的网站上有巧妙的log(m+n)的解法,但对面试来说太难。
: 有人onsite的时候被问过这题么?

avatar
C*U
18
如果是m+n的话,只要用merge那样做就可以了吧。

得太长,怎么简化才能在白板上写的下?

【在 K*****k 的大作中提到】
: 要求in place, 只要求O(m + n)的方法,不需要log(m + n)那个。我写的代码还是觉得太长,怎么简化才能在白板上写的下?
: double GetMedian(int A[], int m, int B[], int n)
: {
: bool odd_length = ((m + n) % 2 == 0)? false : true;
: int m1, m2;
: int pos = (m + n + 1) / 2;
: int count = 0;
: int i = 0;
: int j = 0;
: while (i < m && j < n)

avatar
x*7
19
到底怎么答好呢?leetcode上面找中位数和找kth解法好像不一样吧。
avatar
e*e
21
用merge的方法写了下。
template
T findKthOf2SortedArray1(T P[], int s, T Q[], int t, int k)
{
// assume: 1 <= k <= (s+t)
int i=0, j=0;
for (int l = 0; l < k; l++){
if (i == s) j++;
else if (j == t) i++;
else {
if (P[i] < Q[j]) i++;
else j++;
}
}
if (i == 0) return Q[j-1];
else if (j == 0) return P[i-1];
else return max(P[i-1], Q[j-1]);
}
template
T medianOfTwoSortedArray3(T P[], int s, T Q[], int t)
{
int k = (s + t)/2;
if ( (s+t)%2 == 1 ) return findKthOf2SortedArray1(P,s,Q,t,k+1);
else {
T res1 = findKthOf2SortedArray1(P,s,Q,t,k);
T res2 = findKthOf2SortedArray1(P,s,Q,t,k+1);
return (res1+res2)/2;
}
}

【在 C***U 的大作中提到】
: 如果是m+n的话,只要用merge那样做就可以了吧。
:
: 得太长,怎么简化才能在白板上写的下?

avatar
p*g
22
可惜没有越界检查
这个代码还是不对



【在 f*******t 的大作中提到】
: lgk查找递归方法不长的,我顺便发个收藏的代码吧。记不得作者是谁……
: int findKthFrom2SortedArraysIterative(int *arr1, int *arr2, int k){
: int result;
: int mid;
: int curPosOfArr1 = 0, curPosOfArr2 = 0;
: while(k > 1){
: mid = k/2;
: if(arr1[curPosOfArr1 + mid - 1] < arr2[curPosOfArr2 + mid - 1]){
:
: curPosOfArr1 = curPosOfArr1 + mid;

相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。