给出两个长度为N的有序数组A和B 给出求中位数的算法

港控/mmm° 2022-08-07 07:37 138阅读 0赞

有个同学阿里面试被问到“给出两个长度为N的有序数组A和B 给出求中位数的算法”  怎么办？？很熟悉是吧 但是就是想不起来。。

题目是《算法导论》上的一道习题，不过已多次出现在面试题当中。注意，此题中两个数组的长度是相等的。当然，长度不等的话也可以做，只是要多些判断条件。参考leetcode题目 [Median of Two Sorted Arrays][]

**方法1 直接遍历**

直接的解法是遍历两个数组并计数，类似归并排序里面的有序数组的合并，复杂度为O（n）。代码如下：

#include <iostream>
    #include <stdio.h>
    using namespace std;
    double getMedian(int arr1[],int arr2[], int n){
        int i=0,j=0; //分别是 arr1， arr2的当前下标
        int m1=-1,m2=-1; //保存两个中位数. 由于是2n个，肯定有两个中位数
        for(int cnt=0; cnt<=n; cnt++){
            if( i<n && (arr1[i] < arr2[j] || j >= n ))

{
                m1 = m2;
                m2 = arr1[i++];
            }

else

{
                m1 = m2;
                m2 = arr2[j++];
            }
        }
        return (m1+m2)/2.0;
    }
    int main()
    {
        int ar1[] = {1, 12, 15, 26, 38};
        int ar2[] = {2, 13, 17, 30, 45};
        int n1 = sizeof(ar1)/sizeof(ar1[0]);
        int n2 = sizeof(ar2)/sizeof(ar2[0]);
        if (n1 == n2)
            printf("Median is %lf", getMedian(ar1, ar2, n1));
        else
            printf("Doesn't work for arrays of unequal size");
        return 0;
    }

**方法2 分治法**

要求的复杂度为O(log (m+n))，很显然需要用分治法求解。

假设数组A的中位数为m1，数组B为m2，例如：

ar1\[\] = \{1, 12, 15, 26, 38\}

ar2\[\] = \{2, 13, 17, 30, 45\}

m1 = 15 ，m2 = 17 。由于m1<m2，则可以确定中位数即为下面两个子数组的中位数 ：

\[15, 26, 38\]  和 \[2, 13, 17\]

重复这个步骤，可以得到   m1 = 26 m2 = 13. 得到两个子数组：

\[15, 26\] 和\[13, 17\]

这时，由于n=2，无法在继续分下去了。可以直接计算得：//这里我倒是觉得可以继续分下去 知道子数组里只有一个元素，因此\[15, 26\]得到m1=20.5，\[13, 17\]得到m2=15，得到两个子数组\[15\]和\[17\]，最后就可以求出中位数16

代码如下：

#include<stdio.h>
    #include<algorithm>
    using namespace std;
    int median(int arr[], int n)
    
    {
    
    	if (n%2 == 0)
    		return (arr[n/2] + arr[n/2-1])/2;
    
    	else
    
    		return arr[n/2];
    
    }
    
    
    
    int getMedian(int ar1[], int ar2[], int n) 
    {
    	int m1;
    	int m2;
    	if (n <= 0)
    		return -1;
    	if (n == 1)
    		return (ar1[0] + ar2[0]) / 2;
    	//if (n == 2)
    		//return (max(ar1[0], ar2[0]) + min(ar1[1], ar2[1])) / 2;
    	m1 = median(ar1, n);
    	m2 = median(ar2, n);
    	/* 相等可直接返回 */
    	if (m1 == m2)
    		return m1;
    	if (m1 < m2) <span style="font-family: 'Microsoft YaHei';">{</span>

if (n % 2 == 0)
    		{
    			return getMedian(ar1 + n/2, ar2, n/2 );
    		 }
    		else
    		{
    			return getMedian(ar1 + n/2, ar2, n/2+1);
    		}
    	} 
    	else {
    		if (n % 2 == 0)
    		{
    			return getMedian(ar2 + n/2, ar1, n/2);
    		}
    		else
    		{
    			return getMedian(ar2 + n/2, ar1, n/2+1);
    		}
    	}
    }
    int main()
    {
    	int ar1[] = {1, 12, 10, 26, 38};
    	int ar2[] = {2, 13, 17, 30, 45};
    	int n1 = sizeof(ar1)/sizeof(ar1[0]);
    	int n2 = sizeof(ar2)/sizeof(ar2[0]);
    	if (n1 == n2)
    		printf("Median is %d", getMedian(ar1, ar2, n1));
    	else
    		printf("Doesn't work for arrays of unequal size");
    	return 0;
    }

但是我的输出结果是13，，为什么不是15？？求大神指点 到底哪里出错了。

[Median of Two Sorted Arrays]: https://oj.leetcode.com/problems/median-of-two-sorted-arrays/