题目
There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
You may assume nums1 and nums2 cannot be both empty.
找出两个有序数组的中位数，时间复杂度要求是O(log(m+n))
例子
nums1 = [1, 3]
nums2 = [2]
The median is 2.0
解题思路
- 对时间复杂度要敏感，看到log(m+n)就想到是二分查找，
- 时间复杂度摆在那里，肯定不可能先合并再二分，也要避免多一个数组出现
- 问题可表达为在两个有序数组中找到第k个数字
- 无论如何至少在一个数组中会存在第K/2个数字，；利用二分的思想就可以先在nums1和nums2中淘汰掉k/2个较小的数字，如果有一个没有k/2个字符则表示可以直接淘汰掉另一个数组中的K/2个，因为不管数不够的那个数组（nums1）的那些个数大还是小，第K个数字绝对不会出现在(nums2)中。
- 设置midVal作为二分查找的一个判断条件，1或2往后移k/2个位置，递归得到最后的结果
代码
class Solution {
public:double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {int m = nums1.size(), n = nums2.size(), left = (m + n + 1) / 2, right = (m + n + 2) / 2;return (findKth(nums1, 0, nums2, 0, left) + findKth(nums1, 0, nums2, 0, right)) / 2.0;}int findKth(vector<int>& nums1, int i, vector<int>& nums2, int j, int k) {if (i >= nums1.size()) return nums2[j + k - 1];if (j >= nums2.size()) return nums1[i + k - 1];if (k == 1) return min(nums1[i], nums2[j]);int midVal1 = (i + k / 2 - 1 < nums1.size()) ? nums1[i + k / 2 - 1] : INT_MAX;int midVal2 = (j + k / 2 - 1 < nums2.size()) ? nums2[j + k / 2 - 1] : INT_MAX;if (midVal1 < midVal2) {return findKth(nums1, i + k / 2, nums2, j, k - k / 2);} else {return findKth(nums1, i, nums2, j + k / 2, k - k / 2);}}
};
参考代码
#include <stdio.h>
#include <vector>
using namespace std;#define max(a,b) (((a) > (b)) ? (a) : (b))
#define min(a,b) (((a) < (b)) ? (a) : (b))class Solution {
public:double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {int n = nums1.size();int m = nums2.size();if (n > m) //保证数组1一定最短{return findMedianSortedArrays(nums2, nums1);}// Ci 为第i个数组的割,比如C1为2时表示第1个数组只有2个元素。LMaxi为第i个数组割后的左元素。RMini为第i个数组割后的右元素。int LMax1, LMax2, RMin1, RMin2, c1, c2, lo = 0, hi = 2 * n; //我们目前是虚拟加了'#'所以数组1是2*n长度while (lo <= hi) //二分{c1 = (lo + hi) / 2; //c1是二分的结果c2 = m + n - 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)hi = c1 - 1;else if (LMax2 > RMin1)lo = c1 + 1;elsebreak;}return (max(LMax1, LMax2) + min(RMin1, RMin2)) / 2.0;}
};int main(int argc, char *argv[])
{vector<int> nums1 = { 2,3, 5 };vector<int> nums2 = { 1,4,7, 9 };Solution solution;double ret = solution.findMedianSortedArrays(nums1, nums2);return 0;
}作者：bian-bian-xiong
链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/4-xun-zhao-liang-ge-you-xu-shu-zu-de-zhong-wei-shu/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。