LeedCode 4. 寻找两个正序数组的中位数

中位数"/>

LeedCode 4. 寻找两个正序数组的中位数

一、题目

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。示例 1：输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2示例 2：输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5示例 3：输入：nums1 = [0,0], nums2 = [0,0]
输出：0.00000示例 4：输入：nums1 = [], nums2 = [1]
输出：1.00000示例 5：输入：nums1 = [2], nums2 = []
输出：2.00000提示：nums1.length == mnums2.length == n0 <= m <= 10000 <= n <= 10001 <= m + n <= 2000-106 <= nums1[i], nums2[i] <= 106

二、思路

• 求2个数组的中位数，那么可以看作求两个数组第k小的数，k为(m+n)/2的位置上的数。若(m + n)为奇数，那么中位数就是第(m+n)/2+1小的数，若为偶数，则是第(m+n)/2+1小的数加上第(m+n)/2小的数除以2
• 如何在两个数组上二分求解第k小的数呢。我们可以比较数组A[k/2 - 1]和B[k/2-1]位置上的数，其中较小数前面的数至多有 (k/2-1） + (k/2-1) <= k - 2个数比它小，那么它必然不是第k小的数，就可以去除它前面的数一直到它为止，例如A[k/2-1] > B[k/2-1]，去除 前面的数至k/2-1位置的所有数。
• 分为三种情况
  1.A[k/2-1] < B[k/2-1], 直接去除A数组包括k/2-1索引及其以前的所有数
  2.A[k/2-1] > B[k/2-1] 直接去除B数组包括k/2-1索引及其以前的所有数
  3.A[k/2-1] == B[k/2-1]， 按照第一种情况算即可，因为即使去除了也有相同的值代替。
  每次k减去去除的数，直到k==1时，直接比较两个数组开头位置最下的数返回即可。
• 两种特殊情况
  1. k/2-1的位置上有一方越界，那么用这个数组的最后一个数进行比较
  2. 一个数组的数全部去除了(或者数组为空),那么直接返回另外一个数组的第k个数

三、代码

class Solution {
public:double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {int n = nums1.size(), m = nums2.size();if ((n + m) % 2 == 0) {//是偶数个 那么中位数=(m+n)/2 + (m+n)/2+1的位置的数之和除2return (minK(nums1, nums2, n, m, (m + n) / 2) + minK(nums1, nums2, n, m, (m + n) / 2 + 1)) / 2; } else {return minK(nums1, nums2, n, m, (m + n) / 2 + 1);}}double minK(vector<int>& nums1, vector<int>& nums2, int n, int m, int k) {int l1 = 0, l2 = 0;while (1) {// 若k/2-1越界，那么用最后一个元素替代int k_1 = min(k / 2 - 1 + l1, n - 1), k_2 = min(k / 2 - 1 + l2, m - 1);//判断是否一方为空if (l1 == n) return nums2[k + l2 - 1];if (l2 == m) return nums1[k + l1 - 1];if (k == 1) return min(nums1[l1], nums2[l2]);if (nums1[k_1] <= nums2[k_2]) {k -= k_1 - l1 + 1;l1 = k_1 + 1;} else {//排除这个数组剩余的所有数k -= k_2 - l2 + 1;l2 = k_2 + 1; }}}
};