【LeetCode练习】[困难]4.寻找两个正序数组的中位数

【LeetCode练习】[困难]4. 寻找两个正序数组的中位数

题目来源
算法思想&＃xff1a;有序数组&＃xff0c;中位数

题目&＃xff1a;

java代码–合并两个有序数组&＃xff0c;不符合复杂度

思路: 合并时间空间均为O(m&＃43;n)&＃xff0c;不符合题目O(log(m&＃43;n))

1. 合并两个有序数组&＃xff0c;使之成为一个有序数组,
2. 然后利用排好序的数组&＃xff0c;找到中位数

class Solution {public double findMedianSortedArrays(int[] nums1, int[] nums2) {//合并有序数组int[] res &＃61; merge(nums1, nums1.length, nums2, nums2.length);double ans &＃61; 0.0;//中位数,数组长度分为:奇数和偶数情况if (res.length % 2 &＃61;&＃61; 0) {//偶数ans &＃61; (double)(res[res.length / 2] &＃43; res[res.length / 2 - 1])/2;}else {//奇数ans &＃61; res[res.length / 2];}return ans;}//合并两个有序数组,返回一个有序数组public int[] merge(int[] nums1, int m, int[] nums2, int n) {int[] res &＃61; new int[m&＃43;n];//新数组int i &＃61; 0;int j &＃61; 0;int k &＃61; 0;while (i < m && j < n) {if (nums1[i] <&＃61; nums2[j]) {//如果nums1的数值更小,放入新数组中res[k] &＃61; nums1[i];k&＃43;&＃43;;i&＃43;&＃43;;}else {//如果nums2的数值更小,放入新数组中res[k] &＃61; nums2[j];k&＃43;&＃43;;j&＃43;&＃43;;}}while (i < m) {//如果nums1还有剩余数值,放入新数组中res[k] &＃61; nums1[i];k&＃43;&＃43;;i&＃43;&＃43;;}while (j < n) {//如果nums2还有剩余数值,放入新数组中res[k] &＃61; nums2[j];k&＃43;&＃43;;j&＃43;&＃43;;}return res;//返回新数组}
}


java代码–O(log(m&＃43;n))划分数组

/*https://www.jiuzhang.com/solution/median-of-two-sorted-arrays/#tag-lang-java
快速选择
解题思路对于长度为m的数组A&＃xff0c;我们把A划分成两个部分A1 &＃61; A[0, i-1]和A2 &＃61; A[i, m-1]。对于长度为n的数组B&＃xff0c;将B划分成B1 &＃61; B[0, j-1]和B2 &＃61; B[j, n-1]&＃xff0c;使得len(A1) &＃43; len(B1) &＃61;&＃61; len(A2) &＃43; len(B2)&＃xff08;记作条件1&＃xff09;&＃xff0c;那么当A划分后&＃xff0c;B的划分位置就是确定的。如果我们能够确定max(A1[:], B1[:]) <&＃61; min(A2[:], B2[:])&＃xff08;记作条件2&＃xff09;&＃xff0c;说明我们已经找到合适的划分&＃xff0c;能够把{A, B}分成长度相等的两份&＃xff0c;且一份中的元素全部大于等于另一份。那么&＃xff0c;中位数就为(max(A1[:], B1[:]) &＃43; min(A2[:], B2[:])) / 2。怎么找到满足条件2的划分呢&＃xff1f;选择较短的数组&＃xff0c;假设长度为m&＃xff0c;对它可能的划分位置有m &＃43; 1种。我们可以进行二分搜索&＃xff0c;那么时间复杂度能够进一步优化到O(log(min(m,n))算法流程如果A长度大于B&＃xff0c;两者交换一下&＃xff0c;保证A是更短的。对A进行二分&＃xff0c;low和high初始化为0和m&＃xff0c;每次循环不断缩小二分区间 对A的划分位置partition_x为区间中点low &＃43; (high - low) // 2&＃xff0c;根据条件1计算出B的划分位置partition_y。 我们在划分处的两端&＃xff0c;可以得到四个值&＃xff1a;A左部分的最大值max_left_x&＃xff0c;A右部分的最小值min_right_x&＃xff0c;B左部分的最大值max_left_y&＃xff0c;B右部分的最小值min_right_y。如果某个值不存在&＃xff0c;对于这种边界情况&＃xff0c;我们把最大值设为无穷小&＃xff0c;最小值设为无穷大&＃xff0c;保证后一步的比较恒成立。 如果此刻的划分满足了条件2&＃xff0c;用上述四值来翻译一下就是max_left_x <&＃61; min_right_y and max_left_y <&＃61; min_right_x:&＃xff0c;那么我们就找到了中位数&＃xff0c;是max(max_left_x, max_left_y) &＃43; min(min_right_x, min_right_y)) / 2。 如果不满足&＃xff0c;如果max_left_x > min_right_y&＃xff0c;说明partition_x位置靠右了&＃xff0c;令high &＃61; partition_x - 1&＃xff1b;反之&＃xff0c;说明partition_x位置靠左了&＃xff0c;令low &＃61; partition_x &＃43; 1。继续我们的循环。复杂度分析&＃xff1a;时间复杂度&＃xff1a;O(log(min(m,n))。m和n分别是两个数组的长度。
空间复杂度&＃xff1a;O(1)*/
class Solution {public double findMedianSortedArrays(int[] nums1, int[] nums2) {int lenA &＃61; nums1.length;int lenB &＃61; nums2.length;if (lenA > lenB) return findMedianSortedArrays(nums2, nums1);int halfLen &＃61; (lenA &＃43; lenB - 1) / 2;int left &＃61; 0;int right &＃61; lenA - 1;while (left <&＃61; right) { //int midA &＃61; (left &＃43; right) >> 1; int midA &＃61; (right - left) / 2 &＃43; left;int midB &＃61; halfLen - midA;if (nums1[midA] < nums2[midB]) {left &＃61; midA &＃43; 1;} else {right &＃61; midA - 1;}} int maxLeftA &＃61; (left > 0) ? nums1[left - 1] : Integer.MIN_VALUE;int minRightA &＃61; (left < lenA) ? nums1[left] : Integer.MAX_VALUE;int maxLeftB &＃61; (halfLen - left >&＃61; 0) ? nums2[halfLen - left] : Integer.MIN_VALUE;int minRightB &＃61; (halfLen - left &＃43; 1 < lenB) ? nums2[halfLen - left &＃43; 1] : Integer.MAX_VALUE;if ((lenA &＃43; lenB) % 2 &＃61;&＃61; 1) return (double) Math.max(maxLeftA, maxLeftB);return (Math.max(maxLeftA, maxLeftB) &＃43; Math.min(minRightA, minRightB)) / 2.0;}
}