题目
给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。
请你找出这两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。
示例 1:
nums1 = [1, 3]
nums2 = [2]
则中位数是 2.0
示例 2:
nums1 = [1, 2]
nums2 = [3, 4]
则中位数是 (2 + 3)/2 = 2.5
思路
1.转化为取第k大的数
2.每次从两个数组中取k / 2大的数做比较，去掉小的那一方，更新k直到k=1
实现
class Solution {
public:double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {int m = nums1.size();int n = nums2.size();// 分为奇偶两种情况处理if ((m + n) % 2 == 0) {int a = (m + n + 1) / 2;int b = (m + n + 2) / 2;return (findKth(nums1, 0, m - 1, nums2, 0 , n - 1, a) +findKth(nums1, 0, m - 1, nums2, 0 , n - 1, b)) / 2;}return findKth(nums1, 0, m - 1, nums2, 0 , n - 1, (m + n + 1) / 2);}double findKth(vector<int>& nums1, int s1, int e1, vector<int>& nums2, int s2, int e2, int k) {int len1 = e1 - s1 + 1;int len2 = e2 - s2 + 1;if (len1 <= 0) {return nums2[s2 + k - 1];} if (len2 <= 0) {return nums1[s1 + k - 1];}if (k == 1) return min(nums1[s1], nums2[s2]);// 处理数组长度小于 k / 2的情况int i = min(len1, k / 2);int j = min(len2, k / 2);if (nums1[s1 + i - 1] < nums2[s2 + j - 1]) {return findKth(nums1, s1 + i, e1, nums2, s2, e2, k - i);} return findKth(nums1, s1, e1, nums2, s2 + j, e2, k - j);}
};
参考链接leetcode 4. 寻找两个正序数组的中位数