【LeetCode】4. Median of Two Sorte

2019-12-12 本文已影响0人 LeetPub

题意

找到两个有序数组的中位数

解答一（递归，时间复杂度O(logk)）

$\color{red}{关键点：一步步筛选出k/2个已经确定在k个最小数中的元素}\$

首先理解题意两个关键点：有序数组和中位数

对于有序数组a，长度为m
- 如果m为奇数，则中位数为第m/2+1小的数；
- 如果m为偶数，则中位数为第m/2+1小与第m/2小的数的平均和；
对于有序数组a和b，长度分别为m和n
- 如果m+n为奇数，则两个数组的中位数为第(m+n)/2+1小的数
- 如果m+n为偶数，则两个数组的中位数为第(m+n)/2+1小和第(m+n)/2小的数平均和；

根据上面性质可知，只要找到第(m+n)/2+1小和第(m+n)/2小的数即可，该题演变成找两个有序数组第k小的数；

如何寻找两个有序数组的第k小数？二分查找

先声明查找第k小数的函数

/* param:
 *      a   数组a起始地址
 *      m   数组a起始地址开始的长度
 *      b   数组b起始地址
 *      n   数组b起始地址开始的长度
 */
int findKth(int* a, int m, int* b, int n, int k);

如果i=k/2，则j=k-i=k/2, $a_0..a_{i-1}$ 和 $b_0..b_{j-1}$ 总共k个数，但这k个数不一定是最小的k个数

$a_{i-1} \lt b_{j-1}$
说明 $a_{i}$ 的左边部分肯定在最小的k个数里面， $a_{i}$ 右边部分可能存在数在最小的k个数里面；
这时候需要在 $a_{i}..a_{m-1}$ 和 $b_0..b_{n-1}$ 中查找第 ${k-i}$ 小的数

findKth(a+i, m-i, b, n, k-i);

$a_{i-1} \gt b_{j-1}$
说明 $b_{i}$ 的左边部分肯定在最小的k个数里面， $b_{i}$ 右边部分可能存在数在最小的k个数里面；
这时候需要在 $a_{0}..a_{m-1}$ 和 $b_{j}..b_{n-1}$ 中查找第 ${k-j}$ 小的数

findKth(a, m, b+j, n-j, k-j);

$a_{i-1} = b_{j-1}$
说明找到第k小的数， $a_0..a_{i-1}$ 和 ${b_0..b_{j-1}}$ 总共k个最小的数

二分核心流程：

int i = min(m, k/2), j = k-i;
if (a[i-1] < b[j-1]) {
    return findKth(a+i, m-i, b, n, k-i);
} else if (a[i-1] > b[j-1]) {
    return findKth(a, m, b+j, n-j, k-j);
} else {
    return a[i-1];
}

现在考虑边界情况

${i-1} \ge 0$ 且 ${j-1} \ge 0$
$=>{i} \ge 1$ 且 ${j} \ge 1$
$=>k \ge 2$
所以当k=1时不能进入上面二分核心流程

if (k==1) return min(a[0], b[0]);`

由于要使用a[0]和b[0]，所以a和b必须分别至少有一个元素；如果a没有元素或者b没有元素不能进入k==1的判断条件

if (m == 0) return b[k-1];
if (n == 0) return a[k-1];

$m \le k/2$
$=>{i = m}, j=k-i=k-m \ge 2m-m=m$
$=> j \lt n => m \lt n$
如果m> n，则需要将数组a和b交换

完整代码：

class Solution {
public:
    int findKth(int* a, int m, int* b, int n, int k) {
        if (m > n) return findKth(b, n, a, m, k);
        if (m == 0) return b[k-1];
        if (k == 1) return min(a[0], b[0]);
        int i = min(m, k/2), j = k - i;
        if (a[i-1] < b[j-1]) {
            return findKth(a+i, m-i, b, n, k-i);
        } else if (a[i-1] > b[j-1]){
            return findKth(a, m, b+j, n-j, k-j);
        } else {
            return a[i-1];
        }
    }
    
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size();
        if ((m+n)%2) {
            return findKth(nums1.data(), m, nums2.data(), n, (m+n)/2+1);
        } else {
            int left = findKth(nums1.data(), m, nums2.data(), n, (m+n)/2);
            int right = findKth(nums1.data(), m, nums2.data(), n, (m+n)/2+1);
            cout<<left<<" "<<right<<endl;
            return (left+right)/2.0;
        }
    }
};

解答二（非递归，时间复杂度O(log(min(m,n)))）

$\color{red}{关键点：对一个数组进行二分查找，另一个数组相应的位置也会被相应确定}\$
对于数组 $a_0..a_{m-1}$ ，有 ${m+1}$ 种分隔方式，如下图（a）所示；当 $a$ 的 $a_{left}$ 部分长度为 $i$ 时， $a_{right}$ 部分长度为 ${m-i}$ ，如下图（b）所示；

如果 ${i=0}$ ，则 ${|a_{left}|=0}$ ， ${|a_{right}|=m}$
如果 $i=m$ ，则 ${|a_{left}|=m}$ ， ${|a_{right}|=0}$
如果 ${i \ne0}$ 且 ${i \ne m}$ ，则 ${|a_{left}|=i}$ ， ${|a_{right}|=m-i}$

同样的对于数组 $b_0..b_{n-1}$ ，有 ${n+1}$ 种分隔方式，

如果 ${j=0}$ ，则 ${|b_{left}|=0}$ ， ${|b_{right}|=n}$
如果 $j=n$ ，则 ${|b_{left}|=n}$ ， ${|b_{right}|=0}$
如果 ${j \ne0}$ 且 ${j \ne m}$ ，则 ${|b_{left}|=j}$ ， ${|b_{right}|=n-j}$

如何求数组a和b的中位数？按照上述划分原则，只要把数组a和b划分成left和right两部分，保证 ${|a_{left}|+|b_{left}| = |a_{right}|+|b_{right}| }$ ，同时 ${max({left}) \le min({right})}$ ，左边元素都小于等于右边元素，则中位数为 $\frac{max({left})+min({right})}{2}$ 。

但是数组分偶数和奇数两种情况：

如果 ${m+n}$ 是偶数，只需要 ${left}$ 和 ${right}$ 等分即可，即 ${i+j=m-i+n-j} => {j=\frac{m+n}{2}-i}$ ，又由于整数除法是向下取值的，则 $\frac{m+n}{2}=\frac{m+n+1}{2}$ ，故也满足 ${j=\frac{m+n+1}{2}-i}$ ，中位数为 $\frac{max({left})+min({right})}{2}$ ；
如果 ${m+n}$ 是奇数，将中间元素放到左边，右边将比左边少一个元素，即 ${i+j=m-i+n-j+1} => {j=\frac{m+n+1}{2}-i}$ ，中位数为 $\frac{max({left})}{2}$
$\color{red}{注意：当m+n是奇数时，(m+n+1)/2 \ne (m+n)/2}$

综合上述两个条件，不论m+n是奇数还是偶数，对于数组a和b中位数来说满足j=(m+n+1)/2-i，为了保证 ${ j \ge 0}$ ，则
$\begin{aligned} \frac{m+n+1}{2}-i \ge 0 =>{m+n+1} \ge {2i} => {m+n+1} \ge {2i} \ge {2m} => n \ge m-1 => n \gt m \\ \end{aligned}$

故中位数满足的条件是：

$j=\frac{m+n+1}{2}-i$
${b_{j-1}} \le a_{i}$ 且 ${a_{i-1}} \le b_{j}$

边界条件：
当m+n不论奇数偶数时

当 $i=0$ 时，j=(m+n+1)/2，则最小的数都在数组b， $max({left})=b_{j-1}$
当 $j=0$ 时，i=(m+n+1)/2，则则最小的数都在数组a， $max({left})=a_{i-1}$
当 $i \ne 0$ 且 $j \ne 0$ ，则 $max({left})=max(a_{i-1},b_{j-1})$

当m+n为偶数时，需要 $min(right)$

当 $i=m$ 时，数组a都在左边，右边都是b， $min({right})=b_{j}$
当 $j=n$ 时，数组b都在左边，右边都是a， $min({right})=a_{i}$
当 $i \ne m$ 且 $j \ne n$ ，则 $min({right})=min(a_{i},b_{j})$

当对数组a进行二分查找位置i时，相应的数组b位置j=(m+n+1)/2-i，此时数组a和数组b左右两部分相等，中位数
$media=\left\{ \begin{aligned} \frac{max({left})+min({right})}{2} & & m+n偶数 \\ \frac{max({left})}{2} & & m+n奇数 \\ \end{aligned} \right.$

完整代码：

class Solution {
public:    
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size();
        if (m > n) return findMedianSortedArrays(nums2, nums1);
        int imin = 0, imax = m, i = 0, j = 0, media = 0;
        while (imin <= imax) {
            i = (imin+imax)/2;
            j = (m+n+1)/2 - i;
            if (j-1>=0 && j-1<n && i>=0 && i<m  && nums2[j-1] > nums1[i]) {
                imin = i + 1;
            } else if (i-1>=0 && i-1<m && j>=0 && j< n  && nums1[i-1] > nums2[j]) {
                imax = i - 1;
            } else {    
                if (i == 0) media = nums2[j-1];
                else if (j == 0) media = nums1[i-1];
                else media = max(nums1[i-1], nums2[j-1]);
                break;
            }
        }
        if ((m+n)&1) return media;
        if (i == m) media += nums2[j];
        else if (j == n) media += nums1[i];
        else media += min(nums1[i], nums2[j]);
        return media*0.5;
    }
};

【LeetCode】4. Median of Two Sorte

题意

解答一（递归，时间复杂度O(logk)）

解答二（非递归，时间复杂度O(log(min(m,n)))）

猜你喜欢

热点阅读