【力扣 Hot100 | 第三天】4.12（寻找两个正序数组的中位数）

本文主要是介绍【力扣 Hot100 | 第三天】4.12（寻找两个正序数组的中位数），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

3.1题目

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

• 示例一：

输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2

3.2解法：暴力（归并排序）

• 题目既然给出了两个正序数组，我们可以将这两个正序数组合成为一个正序的数组
• 判断合成后的数组的长度为奇数还是偶数，进而求出中位数
• 归并排序的时间复杂度为 O(m+n)、空间复杂度为 O(m+n)

class Solution {public double findMedianSortedArrays(int[] nums1, int[] nums2) {int len1 = nums1.length;int len2 = nums2.length;// 合成的数组int[] res = new int[len1+len2];int index = 0;int left = 0, right = 0;// 归并排序合成部分while(left<len1&&right<len2) {if(nums1[left]<nums2[right]) {res[index++] = nums1[left++];} else {res[index++] = nums2[right++];}}// 判断nums1剩余还是nums2剩余，并将剩余部分加入到合成的数组之后while(left<len1) {res[index++] = nums1[left++];}while(right<len2) {res[index++] = nums2[right++];}// 判断合成后的数组的长度，求出中位数。返回的是double类型if((len1+len2)%2==1) {return (double) res[(len1+len2)/2];} else {return (double) (res[(len1+len2)/2]+res[(len1+len2)/2-1])/2;}}
}

3.3解法：二分法

1. 暴力解法对于本题来说不满足时间复杂度，要求时间复杂度为O(log(m+n))，所以自然想到了二分法。

2. 理解：

   1. 两个数组长度为奇数，则中位数即为第 (m+n)/2+1 小 元素；
   2. 两个数组长度为偶数，则中位数即为第 (m+n)/2 小元素 和 第 (m+n)/2+1 小元素；

3. 归纳：如何求出两个数组中第k小的元素？

   1. 首先需要找到 第一个数组中的k/2位置、第二个数组的k/2位置；

   2. 如果 nums1[k/2] < nums2[k/2] ，则 nums1[k/2]及其前面的元素均不是第k小，所以我们应该从 nums1[k/2+1] 到末尾，以及nums2中查找

      1. why？

      2. 理由：比nums1[k/2]小的数字有 k/2-1个，比nums2[k/2]小的数字有 k/2-1个；

         又又 nums1[k/2] < nums2[k/2]

         即 比nums2[k/2]小的数字最小有 （k/2-1）+（k/2-1）+1= k-1个

         即nums1[k/2]最多是第k-1个数，它及其前面的肯定不是第k个数，所以需要去掉

   3. 如果 nums1[k/2] > nums2[k/2]，则 nums2[k/2]及其后面的元素均不是第k小，所以我们应该从 nums1 以及 nums2[k/2+1]到末尾中查找

4. 例子：

   

public double findMedianSortedArrays(int[] nums1, int[] nums2) {int n = nums1.length;int m = nums2.length;int left = (n + m + 1) / 2;int right = (n + m + 2) / 2;//将偶数和奇数的情况合并，如果是奇数，会求两次同样的 k 。return (getKth(nums1, 0, n - 1, nums2, 0, m - 1, left) + getKth(nums1, 0, n - 1, nums2, 0, m - 1, right)) * 0.5;  
}private int getKth(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int k) {int len1 = end1 - start1 + 1;int len2 = end2 - start2 + 1;//让 len1 的长度小于 len2，这样就能保证如果有数组空了，一定是 len1 if (len1 > len2) return getKth(nums2, start2, end2, nums1, start1, end1, k);if (len1 == 0) return nums2[start2 + k - 1];if (k == 1) return Math.min(nums1[start1], nums2[start2]);int i = start1 + Math.min(len1, k / 2) - 1;int j = start2 + Math.min(len2, k / 2) - 1;if (nums1[i] > nums2[j]) {return getKth(nums1, start1, end1, nums2, j + 1, end2, k - (j - start2 + 1));}else {return getKth(nums1, i + 1, end1, nums2, start2, end2, k - (i - start1 + 1));}
}

这篇关于【力扣 Hot100 | 第三天】4.12（寻找两个正序数组的中位数）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---