https://leetcode-cn.com/problems/median-of-two-sorted-arrays/
给定两个大小为 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
示例 3:
输入:nums1 = [0,0], nums2 = [0,0] 输出:0.00000 示例 4:
输入:nums1 = [], nums2 = [1] 输出:1.00000
示例 5:
输入:nums1 = [2], nums2 = [] 输出:2.00000
提示:
nums1.length == m nums2.length == n 0 <= m <= 1000 0 <= n <= 1000 1 <= m + n <= 2000 -106 <= nums1[i], nums2[i] <= 106 通过次数268,312提交次数691,163
代码有点长,思路很简单; 思路: 1、如果nums1为空,那么只需要查找第二个数组的中位数 2、如果nums2为空,那么只需要查找第一个数组的中位数 3、如果都不为空,就合并nums1和nums2,然后对合并后的数组做查找中位数的操作
package 其他.每日一题;
import java.util.Arrays;
class Solution {
static public double findMedianSortedArrays(int[] nums1, int[] nums2) {
if(nums1.length==0)
return findMidArrays(nums2);
if(nums2.length==0)
return findMidArrays(nums1);
int[] hebing = hebing(nums1, nums2);
// System.out.println("合并好的数组:"+Arrays.toString(hebing));
return findMidArrays(hebing);
}
//合并数组
private static int[] hebing(int[] nums1, int[] nums2){
int len1 = nums1.length;
int len2 = nums2.length;
int[] newIntArray = new int[len1+len2];
int newIndex = 0;
int i = 0;
int j = 0;
while (len1!=0 && len2!=0){
if(nums1[i]>nums2[j]){
newIntArray[newIndex]=nums2[j];
len2--;
j++;
}else{
newIntArray[newIndex]=nums1[i];
len1--;
i++;
}
newIndex++;
}
// System.out.println(Arrays.toString(newIntArray));
//合并剩余的
if(len1!=0){
for (int k = i; k < nums1.length; k++) {
newIntArray[newIndex]=nums1[k];
newIndex++;
}
}
if(len2!=0){
for (int k = j; k < nums2.length; k++) {
newIntArray[newIndex]=nums2[k];
newIndex++;
}
}
// System.out.println(Arrays.toString(newIntArray));
return newIntArray;
}
//查找一个单独的数组中的中位数
private static double findMidArrays(int[] nums) {
if(nums.length==2){
return nums[0]+nums[1]==0?0:(nums[0]+nums[1]) / 2.0;
}
double midNumber = 0;
// int number = (nums.length-1)/2;
int numsLen = nums.length;
//有偶数个
if(numsLen%2==0){
int len = numsLen / 2;
midNumber = (nums[len] + nums[len-1]) / 2.0;
//有奇数个
}else{
numsLen = (nums.length/2)+1;
midNumber = nums[numsLen-1];
}
return midNumber;
}
public static void main(String[] args) {
System.out.println(findMedianSortedArrays(new int[]{1,2,3,4,5,6},new int[]{}));
System.out.println(findMedianSortedArrays(new int[]{1,3},new int[]{2}));
}
}