|
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。
示例 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
在开始讲之前，首先声明这个题是有难度的，在力扣的等级中是困难，所以理解起来比较费劲。这里我想将我看到这道题的思考过程给记录下来，所以可能过程会有点点繁琐和混乱。
思路分析：
- 看到这个题目的时候，我首先看到的是中位数，中位数就是指中间位置的数，根据情况不同，可以分为奇数和偶数的情况
- 如果是奇数，那么最终表示的应该是：
mid=(nums1.length + nums2.length + 1)/2 - 如果是偶数，那么最终表示的应该是：
mid=(num1.length + nums2.length + 1)/2 +(num1.length + nums2.length +2)/2 - 但是我本人比较懒，不想分情况讨论，所以使用了另外一种方式，都是用
mid=(num1.length + nums2.length + 1)/2 +(num1.length + nums2.length +2)/2方式表示。
- 从现在开始，这个题就变成了我们要在两个数组中找到大小排在mid位这个数。（等同于新建一个数组，将其进行排序，然后找到这个mid位次的数）。
- 为了不进行新创建数组，所以我采用新建两个指针来指向这两个数组的其实位置，从而进一步降低时间复杂度。
- 现在开始考虑如何去寻找这个值，这里我有两种思路：
- 第一种，就是我们通过指针一个个遍历，因为我们只需要拿到中位数，所以相当于我们通过指针进行排序，只是不去保存排序结果，最后去找到所对应的位次的数字即可，这种方法是暴力解决，但是时间复杂度不满足要求。
- 第二种思路是通过二分法进行查找。
- 我们是需要找到第k（后面mid都用k来代替）个数，所以通过对k的二分，就是变为了我们要在俩数组中查找第K/2个元素。
- 这个时候有一点是需要注意的，就是可能有一个较短的数组没有（k/2）个数，若果没有就赋值为最大值。
- 若果midNum1 > midNum2，就说明我需要的数字绝对不再num2的（k/2）个数前面。反之亦然。
- 进行反复递归最终找到答案。
- 最后开始考虑边界条件。
- 如果一个数组的起始指针的位置大于这个数组的长度，就说明这个数组为null，就变成了从另外一个数组中找。
- 如果k=1，就直接进行比较俩数组的起始位置的数字的大小即可。
代码实现
public class Solution4 {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.length;
int n = nums2.length;
int left = (m + n + 1) / 2;
int right = (m + n + 2) / 2;
return (findNumber(nums1, 0, nums2, 0, left) + findNumber(nums1, 0, nums2, 0, right)) / 2.0;
}
public int findNumber(int[] nums1, int i, int[] nums2, int j, int k) {
if (i >= nums1.length) {
return nums2[j + k - 1];
}
if (j >= nums2.length) {
return nums1[i + k - 1];
}
if (k == 1) {
return Math.min(nums1[i], nums2[j]);
}
int midNum1 = (i + k / 2 - 1 < nums1.length) ? nums1[i + k / 2 - 1] : Integer.MAX_VALUE;
int midNum2 = (j + k / 2 - 1 < nums2.length) ? nums2[j + k / 2 - 1] : Integer.MAX_VALUE;
if (midNum1 > midNum2) {
return findNumber(nums1, i, nums2, j + k / 2, k - k/2);
} else {
return findNumber(nums1, i +k / 2, nums2, j, k - k/2);
}
}
}
|