算法分析与设计►未分类

Find-Median

  • 问题来源
  • 问题简介

    给定两个有序数组a[m], b[n]，找出中位数
    要求时间复杂度为O(log(m+n))

解题思路

  • 将两个有序数组合成一个有序数组。

这种方法虽然可行，但我们只想找出中位数而已，排序就做了多余的操作了。
  • 找出位于中间的数

这听起来像是废话。。其实，中位数就是位于中间的数，并不需要知道其两边数是否已正确的顺序排列。
令两个数组为a，b且令其满足length_of_a <= length_of_b
于是，我们可以将a分成两部分 leftpart_of_a, rightpart_of_a ，将b分成两部分 leftpart_of_b, rightpart_of_b 。
令 leftpart 由 leftpart_of_a + leftpart_of_b 组成， rightpart 由 rightpart_of_a + rightpart_of_b组成
这样，只要 leftpart中的数都比rightpart小 且 长度相差不大于1 ，
则


  • 当总长度为奇数时，中位数为 右半部分的最小


  • 当总长度为偶数时，中位数为 左半部分的最大和右半部分的最小的一半


时间复杂度 空间复杂度
O(log(m+n)) O(1)

Code

#include <iostream>
#include <algorithm>
using namespace std;

double middle_of_two_sorted_arrays(int *a, int l_a, int *b, int l_b) {
    if (l_a > l_b) {
        // 保证a数组的长度小于等于b数组
        swap(a, b);
        swap(l_a, l_b);
    }

    int b_l = 0, b_r = l_a, half_len = (l_a + l_b) / 2;
    int i, j;
    double zws_l = 0, zws_r = 0;

    if (l_a == 0 && l_b == 0) {
        throw "invalid length";
    } else if (l_a == 0) {
        zws_l = b[l_b/2-1];
        zws_r = b[l_b/2];
        if (l_b & 1) {
            return zws_r;
        }
        return (zws_l + zws_r) / 2;
    }

    /*
        从a中尝试挑选分割点，i的取值 [0, m]
        i 将 a 分成 左右两部分: leftpart_of_a, rightpart_of_a
        j 将 b 分成 左右两部分: leftpart_of_b, rightpart_of_b
        令leftpart由 leftpart_of_a + leftpart_of_b 组成
        令rightpart 由 rightpart_of_a + rightpart_of_b组成
        若 分割点 i，j 使得 leftpart 中的所有数都小于 rightpart 中的所有数
        即 a[i-1] <= b[j] && b[j-1] <= a[i]
        且 |length_of_leftpart - length_of_rightpart| <= 1
        则 i 为目标分割点
        否则，
        若左半部分中存在比右半部分大的数，则意味着分割点
    */

    while (b_l <= b_r) {

        i = (b_l + b_r) / 2;
        j = half_len - i;

        /*
            a 的两个部分 [0, i - 1], [i, length_of_a - 1]
            b 的两个部分 [0, j - 1], [j, length_of_b -1]
        */

        if (i < l_a && a[i] < b[j - 1]) {
            // 分割点过小使得a中本应在左半部分中的数被分到了右半部分
            b_l = i + 1;
            continue;
        }
        if (i > 0 && a[i - 1] > b[j]) {
            // 分割点过大使得a中本应在右半部分中的数被分到了左半部分
            b_r = i - 1;
            continue;
        }

        if (i == 0) {
            zws_l = b[j - 1];
            zws_r = j < l_b ? min(b[j], a[0]) : a[0];
        }
        else if (i == l_a) {
            zws_l = j == 0 ? a[l_a-1] : max(a[l_a-1], b[j-1]);
            zws_r = b[j];
        }
        else {
            zws_l = max(a[i-1], b[j-1]);
            zws_r = min(a[i], b[j]);
        }


        if ((l_a + l_b) & 1) {
            return zws_r;
        }
        return (zws_l + zws_r) / 2;

    }
    throw "invalid length";
}

int main() {
    int arr1[] = { 1, 2, 3, 4 },
        arr2[] = { 5, 6, 7, 8 },
        arr4[] = { 5, 6, 7, 8, 9 },
        arr5[] = { 1, 3, 5, 7, 8 },
        arr6[] = { 2, 3, 4, 6, 10, 11 };

    cout << middle_of_two_sorted_arrays(arr1, 4, arr2, 4) << endl;
    cout << middle_of_two_sorted_arrays(arr1, 4, arr4, 5) << endl;
    cout << middle_of_two_sorted_arrays(arr5, 5, arr6, 6) << endl;
    cout << middle_of_two_sorted_arrays(arr5, 5, arr4, 5) << endl;
    return 0;
}

运行结果

Find-Median