给定两个大小分别为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/median-of-two-sorted-arrays
写法一:
class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { int num1 = nums1.length; int num2 = nums2.length; int[] totalnums = new int[num1 + num2]; for (int i = 0; i < num1; i ++){ totalnums[i] = nums1[i]; } for (int i = 0; i <num2; i ++){ totalnums[num1 + i] = nums2[i]; } for (int i = 0; i < totalnums.length; i ++ ){ for (int j = 0;j < totalnums.length - 1 - i; j ++){ if (totalnums[j] > totalnums[j + 1]){ int temp = totalnums[j]; totalnums[j] = totalnums[j + 1]; totalnums[j + 1] = temp; } } } if ((totalnums.length) % 2 == 1){ return totalnums[(totalnums.length)/2]; }else { return (double) (totalnums[(totalnums.length)/2] + totalnums[(totalnums.length)/2-1])/2; } } }
写法二:
二分查找法(官方解)
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; } }
标签:正序,--,int,length,totalnums,LetCode,nums1,nums2 From: https://www.cnblogs.com/xinger123/p/16633280.html