LeetCode | 4 两个排序数组的中位数

题目

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。找出这两个有序数组的中位数。要求算法的时间复杂度为O(log(m+n))。

示例

• nums1 = [1, 3]，nums2 = [2]，中位数是 2.0；
• nums1 = [1, 2]，nums2 = [3, 4]，中位数是 2.5；

题解

整体上是一个分而治之的思想，将问题分解，使用递归可以很方便的完成。这个问题是『寻找两个有序数组中的第 k 大元素』问题的特殊形式，我们直接实现寻址第 k 大元素的函数 find_kth() 即可，然后在 findMedianSortedArrays() 中调用它即可。

我们使用递归方式实现 find_kth()，对于递归算法，我们要注意递归终止条件。首先要确保第一个参数数组的长度是较短的，

• 较短数组 a 的长度（未搜索区域长度）变为 0，返回 b 中第 k 个元素；
• 待寻找的序数 k = 1，返回a 和 b 的第一个元素中的较小者。

然后我们需要确定每个数组的搜索长度。对于较小数组 a，搜索长度为数组长和 k/2 的较大者，余下的长度则为数组 b 待搜索的长度。

代码如下：

LeetCodeSolution4.cview raw

// 辅助函数 选择两个有序数组中第 k 大的数
int find_kth(int *a, int alen, int *b, int blen, int k)
{
    // 确保 alen < blen
    if (alen > blen)
        return find_kth(b, blen, a, alen, k);
    if (alen == 0)
        return b[k-1];
    if (k == 1)
        return a[0] < b[0] ? a[0] : b[0];

    int ia = alen > k/2 ? k/2 : alen;
    int ib = k - ia;

    if (b[ib-1] > a[ia-1])
        return find_kth(a+ia, alen-ia, b, blen, k-ia);
    else if (b[ib-1] < a[ia-1])
        return find_kth(a, alen, b+ib, blen-ib, k-ib);
    else // 注意这种情况
        return a[ia-1];
}
// 找出两个有序数组中的中位数
double findMedianSortedArrays(int *nums1, int nums1Size,
                        int *nums2, int nums2Size)
{
    int mid = nums2Size + (nums1Size - nums2Size) / 2;
    // if ((nums1Size & 0x1) ^ (nums2Size & 0x1)) // 和为奇数
    if ((nums1Size+nums2Size) & 0x1)
        return find_kth(nums1, nums1Size, nums2, nums2Size, mid+1);
    else    // 和为偶数
        return (find_kth(nums1, nums1Size, nums2, nums2Size, mid)
                    + find_kth(nums1, nums1Size, nums2, nums2Size, mid+1)) / 2.0;
}