题目链接

原题点击此处

思路

  • 题目要求时间复杂度O(log(n + m)), 一次遍历肯定不行,所以采用二分
  • 每次排除k / 2 个元素
  • 原题解链接

代码

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size(), m = nums2.size();
        int l = (n + m + 1) / 2;
        int r = (n + m + 2) / 2;
        //l和r这样取值是为了避免奇数和偶数的情况
        int num1 = getK(nums1, 0, n - 1, nums2, 0, m - 1, l);
        int num2 = getK(nums1, 0, n - 1, nums2, 0, m - 1, r);
        return (num1 + num2) * 1.0/ 2;
    }

    int getK(vector<int>& nums1, int st1, int ed1, vector<int>& nums2, int st2, int ed2, int k) {
        int n = ed1 - st1 + 1, m = ed2 - st2 + 1;
        //保证nums2肯定不为空,方便处理
        if (n > m) return getK(nums2, st2, ed2, nums1, st1, ed1, k);
        if (n == 0) return nums2[st2 + k - 1];
        if (k == 1) return min(nums1[st1], nums2[st2]);
        
        //注意超出数组边界的情况
        int l = min(st1 + k / 2 - 1, ed1);
        int r = min(st2 + k / 2 - 1, ed2);
        if (nums1[l] > nums2[r]) {
            return getK(nums1, st1, ed1, nums2, r + 1, ed2, k - (r - st2 + 1));
        } else {
            return getK(nums1, l + 1, ed1, nums2, st2, ed2, k - (l - st1 + 1));
        }
    }
};
最后修改:2021 年 04 月 03 日 10 : 17 PM