此文章最先发布于我的个人博客，简书为同步发布，如有需要，请访问 腿短快跑的个人博客 获取更多内容
题目描述
给定两个大小分别为 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
提示
- nums1.length == m
- nums2.length == n
- 0 <= m <= 1000
- 0 <= n <= 1000
- 1 <= m + n <= 2000
- -10⁶ <= nums1[i], nums2[i] <= 10⁶
题解
合并数组
思路
- 将两个有序数组合并为一个大的有序数组
- 返回大的有序数组的中位数
实现
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
// 合并两个数组
int[] bigArray = new int[nums1.length + nums2.length];
int i = 0;
int j = 0;
int index = 0;
while (index < nums1.length + nums2.length) {
if (i >= nums1.length) {
bigArray[index++] = nums2[j++];
} else if (j >= nums2.length) {
bigArray[index++] = nums1[i++];
} else {
if (nums1[i] <= nums2[j]) {
bigArray[index++] = nums1[i++];
} else {
bigArray[index++] = nums2[j++];
}
}
}
// 返回中位数
if (bigArray.length % 2 == 0) {
return ((double) bigArray[bigArray.length / 2 - 1] + (double) bigArray[bigArray.length / 2]) / 2;
} else {
return (double) bigArray[bigArray.length / 2];
}
}
}
复杂度分析
时间复杂度：，主要为合并两个有序数组的时间，两个数组均会遍历一遍
空间复杂度：，主要为存储原数组和合并后的数组的空间
性能
执行耗时:1 ms，击败了100.00% 的Java用户
内存消耗:42 MB，击败了85.82% 的Java用户
找中位数的位置
思路
上述实现中我们合并了数组，但是由于两个数组都是有序的，我们只需要找到中位数的位置，然后进行遍历即可
实现
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
// 找到中位数的位置
int total = nums1.length + nums2.length;
int sum = 0;
int index1 = 0;
int index2 = 0;
boolean even = total % 2 == 0;
// 开始遍历数据
for (int i = 0; i < total; i++) {
int num;
if (index1 >= nums1.length) {
num = nums2[index2++];
} else if (index2 >= nums2.length) {
num = nums1[index1++];
} else {
if (nums1[index1] <= nums2[index2]) {
num = nums1[index1++];
} else {
num = nums2[index2++];
}
}
if (even && (i == total / 2 - 1 || i == total / 2)) {
sum += num;
} else if (!even && i == total / 2) {
sum += num;
}
}
return even ? ((double) sum) / 2 : sum;
}
}
复杂度分析
时间复杂度：，主要为合并两个有序数组的时间，两个数组均会遍历一遍
空间复杂度：，主要为原数组的空间大小
性能
执行耗时:1 ms，击败了100.00% 的Java用户
内存消耗:42 MB，击败了84.02% 的Java用户
划分数组
思路
此处记录一下已经看懂的思路，但是代码具体实现我没有看懂，有看懂的小伙伴可以评论告诉我
中位数的作用就是将数组划分为两部分，前半部分最大值 <= 中位数，后半部分最小值 >= 中位数
- 将两个数组进行划分
- 划分后分别合并为前半部分和后半部分
- 确保前半部分的最大值 <= 后半部分的最小值
- 当两个数组的长度和为偶数时，前半部分长度 = 后半部分长度
- 当两个数组的长度和为奇数时，前半部分长度 = 后半部分长度 + 1
实现
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
if (nums1.length > nums2.length) {
return findMedianSortedArrays(nums2, nums1);
}
int m = nums1.length;
int n = nums2.length;
int left = 0, right = m;
// median1：前一部分的最大值
// median2：后一部分的最小值
int median1 = 0, median2 = 0;
while (left <= right) {
// 前一部分包含 nums1[0 .. i-1] 和 nums2[0 .. j-1]
// 后一部分包含 nums1[i .. m-1] 和 nums2[j .. n-1]
int i = (left + right) / 2;
int j = (m + n + 1) / 2 - i;
// nums_im1, nums_i, nums_jm1, nums_j 分别表示 nums1[i-1], nums1[i], nums2[j-1], nums2[j]
int nums_im1 = (i == 0 ? Integer.MIN_VALUE : nums1[i - 1]);
int nums_i = (i == m ? Integer.MAX_VALUE : nums1[i]);
int nums_jm1 = (j == 0 ? Integer.MIN_VALUE : nums2[j - 1]);
int nums_j = (j == n ? Integer.MAX_VALUE : nums2[j]);
if (nums_im1 <= nums_j) {
median1 = Math.max(nums_im1, nums_jm1);
median2 = Math.min(nums_i, nums_j);
left = i + 1;
} else {
right = i - 1;
}
}
return (m + n) % 2 == 0 ? (median1 + median2) / 2.0 : median1;
}
}
