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

原题解地址

题目

给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。 请你找出这两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。 你可以假设 nums1 和 nums2 不会同时为空。

样例

nums1 = [1, 3] nums2 = [2] 则中位数是 2.0

提示：

如果分割两个有序数组后，左半边全小于右半边，如果左边的元素个数相加刚好等于k, 那么第k个元素就是Max(LMax1, LMax2)若LMAX1>RMIN2可以通过减小数组1的割，即增大数组2的割，尝试中位数可以通过向数组元素增加分隔符，来避免单双数的问题 class Solution { public: double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { int n = nums1.size(); int m = nums2.size(); if(n > m) { return findMedianSortedArrays(nums2, nums1); } int LMAX1, LMAX2, RMIN1, RMIN2, start = 0, end = 2 * n, c1, c2; while(start <= end) { c1 = (start + end) / 2; c2 = n + m - c1; LMAX1 = (c1 == 0) ? INT_MIN : nums1[(c1 - 1) / 2]; RMIN1 = (c1 == 2 * n) ? INT_MAX : nums1[c1 / 2]; LMAX2 = (c2 == 0) ? INT_MIN : nums2[(c2 - 1) / 2]; RMIN2 = (c2 == 2 * m) ? INT_MAX : nums2[c2 / 2]; if(LMAX1 > RMIN2) { end = c1 - 1; } else if(LMAX2 > RMIN1) { start = c1 + 1; } else{ break; } } return (max(LMAX1, LMAX2)+min(RMIN1, RMIN2))/2.0; } };