寻找两个正序数组的中位数

描述

给定两个大小分别为 $m$ 和 $n$ 的正序（从小到大）数组 $nums1$ 和 $nums2$。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 $O(log (m+n))$ 。

思路

两个数组是有序的，可以使用双指针对两个数组进行合并，直到合并后的数组达到中位位数长度，此时即可得到两数组的中位数，但是这种方法实际上的复杂度为 $O(m+n)$，不满足题目要求，需要进一步考虑。

由于题目给出的目标时间复杂度存在 $log$，可以推断需要使用二分法。

这里假设中位数为第K个数，分别对两个数组求其第 K/2 - 1 个数，较小的那个数组即可排除掉前 K/2 - 1 个数字，然后更新K值，重复上述步骤。之所以能够排除 K/2 - 1 个数字，是因为最多只有 K - 2 个数字小于等于较小值（包含较小值自身），中位数必不包含在内，因此可以直接将这些数值排除。

代码

class Solution {
private:
    double findKth(const vector<int>& nums1, const vector<int>& nums2, size_t k) {
        size_t m = nums1.size();
        size_t n = nums2.size();

        size_t border1 = 0;
        size_t border2 = 0;

        while (true) {
            if (border1 == m) {
                return nums2[border2 + k - 1];
            }
            if (border2 == n) {
                return nums1[border1 + k - 1];
            }
            if (k == 1) {
                return min(nums1[border1], nums2[border2]);
            }

            const size_t div1 = min(border1 + k / 2 - 1, m - 1);
            const size_t div2 = min(border2 + k / 2 - 1, n - 1);
            const int elem1 = nums1[div1];
            const int elem2 = nums2[div2];

            if (elem1 >= elem2) {
                k -= div2 - border2 + 1;
                border2 = div2 + 1;
            }
            else if (elem1 < elem2) {
                k -= div1 - border1 + 1;
                border1 = div1 + 1;
            }
        }
    }

public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        vector<int> res;

        if ((nums1.size() + nums2.size()) % 2 == 1) {
            return findKth(nums1, nums2, (nums1.size() + nums2.size()) / 2 + 1);
        }
        else {
            return (findKth(nums1, nums2, (nums1.size() + nums2.size()) / 2) + findKth(nums1, nums2, (nums1.size() + nums2.size()) / 2 + 1)) / 2;
        }
    }
};

运行结果

参考

寻找两个有序数组的中位数-官方题解