068寻找两个正序数组的中位数

寻找两个正序数组的中位数题目链接https://leetcode.cn/problems/median-of-two-sorted-arrays/description/?envTypestudy-plan-v2envIdtop-100-liked我的解答无分析自己没什么思路能实现O(log(mn))的解答。看了官方题解后的解答//方法一二分查找只看思路自己实现版 //时间复杂度O(log(mn)) //空间复杂度O(1) public double findMedianSortedArrays(int[] nums1, int[] nums2) { int len1 nums1.length, len2 nums2.length; int n len1 len2; // 将问题转化为了找第k小的元素 int k n % 2 0 ? n/2 : n/21; int l 0, ll 0; while(l len1 ll len2 k 1){ int offset k/2 - 1; int r l offset; int rr ll offset; // 越界情况取最后一个元素 if(r len1){ r len1 - 1; } if(rr len2){ rr len2 - 1; } // 比较并剪枝 if(nums1[r] nums2[rr]){ k - (r 1 - l); l r 1; } else{ k - (rr 1 - ll); ll rr 1; } } int num1 0, num2 0; if(l len1){ num1 nums2[ll k - 1]; num2 ll k len2 ? nums2[ll k] : 0; } else if(ll len2){ num1 nums1[l k - 1]; num2 l k len1 ? nums1[l k] : 0; } else if(k 1){ if(nums1[l] nums2[ll]){ num1 nums1[l]; num2 l 1 len1 nums1[l1] nums2[ll] ? nums1[l1] : nums2[ll]; } else{ num1 nums2[ll]; num2 ll1 len2 nums2[ll1] nums1[l] ? nums2[ll1] : nums1[l]; } } else{ } if(n % 2 ! 0){ return num1; } return (num1 num2) / 2.0; } //方法一二分查找看了官方解答版 //时间复杂度O(log(mn)) //空间复杂度O(1) public double findMedianSortedArrays(int[] nums1, int[] nums2) { int length1 nums1.length, length2 nums2.length; int totalLength length1 length2;//两个数组的总长度 //总长度为奇数 if(totalLength % 2 1){ int midIndex totalLength / 2; double median getKthNum(nums1, nums2, midIndex1); return median; } else{ int midIndex totalLength / 2 - 1; double median (getKthNum(nums1, nums2, midIndex 1) getKthNum(nums1, nums2, midIndex 2)) / 2.0; return median; } } //返回两个数组第K小的元素 public int getKthNum(int[] nums1, int[] nums2, int k){ int length1 nums1.length, length2 nums2.length; int index1 0, index2 0; while(true){ //nums1遍历完了 if(index1 length1){ return nums2[index2 k - 1]; } //nums2遍历完了 if(index2 length2){ return nums1[index1 k - 1]; } //返回nums1[index1]和nums2[index2]中较小的那个 if(k 1){ return Math.min(nums1[index1], nums2[index2]); } //正常情况 int half k / 2; int newIndex1 Math.min(index1 half, length1) - 1; int newIndex2 Math.min(index2 half, length2) - 1; int value1 nums1[newIndex1]; int value2 nums2[newIndex2]; // nums1[0, newIndex1]都不可能是第k小的数 if(value1 value2){ k - (newIndex1 - index1 1); index1 newIndex1 1; } // nums2[0, newIndex2]都不可能是第k小的数 else{ k - (newIndex2 - index2 1); index2 newIndex2 1; } } } //方法二划分数组 //时间复杂度O(log min(m,n)) //空间复杂度O(1) public double findMedianSortedArrays(int[] nums1, int[] nums2) { int m nums1.length, n nums2.length; if(m n){ return findMedianSortedArrays(nums2, nums1); } int l0, rm;//第一个数组假设为A一共有m1个划分点 int leftMax0, rightMin0;//leftMax新左部分的最大值 rightMin新右部分的最小值 while(lr){ int i (lr) / 2; //由于要确保划分后新左部分的长度lengthL与新右部分的长度lengthR满足lengthL lengthR 或 lengthL lengthR1 //所以可以直接根据i的取值计算出满足条件的j int j (mn1)/2 - i; //计算nums1[i-1]、nums1[i]、nums2[j-1]、nums2[j]的取值主要注意边界条件的情况不能影响新左部分的最大值与新右部分的最小值 //num_im1、num_i、num_jm1、num_j分别表示nums1[i-1]、nums1[i]、nums2[j-1]、nums2[j] int num_im1 i0 ? Integer.MIN_VALUE : nums1[i-1]; int num_i im ? Integer.MAX_VALUE : nums1[i]; int num_jm1 j0 ? Integer.MIN_VALUE : nums2[j-1]; int num_j jn ? Integer.MAX_VALUE : nums2[j]; if(num_im1 num_j){ l i 1; leftMax Math.max(num_im1, num_jm1); rightMin Math.min(num_i, num_j); } else{ r i - 1; } } return (mn)%20 ? (leftMaxrightMin) / 2.0 : leftMax; }分析​ 1、方法一的解题思路根据两个数组的长度我们可以知道中间位置下标假设两个数组合并了所以问题就转化成了在两个正序数组中寻找第k小的元素假设中间位置为k-1若两个数组的总长度为奇数那么第k小的元素就是中位数若两个数组的总长度为偶数那么第k小的元素与第k1小的元素之和的一半就是中位数。所以我们把“在两个正序数组中找第k小的元素”单独抽出成一个方法便于复用现在的问题就是如何实现这个方法。以下为实现这个方法的思路分析​ 假设两个有序数组分别是 A 和 B。要找到第 k 个元素我们可以比较 A[k/2−1] 和 B[k/2−1]其中 / 表示整数除法。由于 A[k/2−1] 和 B[k/2−1] 的前面分别有 A[0…k/2−2] 和 B[0…k/2−2]即 k/2−1 个元素对于 A[k/2−1] 和 B[k/2−1] 中的较小值最多只会有 (k/2−1)(k/2−1)≤k−2 个元素比它小那么它就不能是第 k 小的数了。因此我们可以归纳出三种情况​ 如果 A[k/2−1]B[k/2−1]则比 A[k/2−1] 小的数最多只有 A 的前 k/2−1 个数和 B 的前 k/2−1 个数即比 A[k/2−1] 小的数最多只有 k−2 个因此 A[k/2−1] 不可能是第 k 个数A[0] 到 A[k/2−1] 也都不可能是第 k 个数可以全部排除。​ 如果 A[k/2−1]B[k/2−1]则可以排除 B[0] 到 B[k/2−1]。​ 如果 A[k/2−1]B[k/2−1]则可以归入第一种情况处理。​ 有以下三种情况需要特殊处理​ 如果 A[k/2−1] 或者 B[k/2−1] 越界那么我们可以选取对应数组中的最后一个元素。所以我们必须根据排除数的个数减少 k 的值而不能直接将 k 减去 k/2。​ 如果一个数组为空说明该数组中的所有元素都被排除我们可以直接返回另一个数组中第 k 小的元素。​ 如果 k1我们只要返回两个数组首元素的最小值即可。​ 2、方法二的解题思路中位数的本质是将不递减的一组数分成左、右两部分左边与右边的长度之差不超过1且左边的任何一个数不大于右边的任何一个数即左边的最大值小于或等于右边的最小值。基于这个性质我们可以对两个正序数组进行划分找到新左部分的长度lengthL与新右部分的长度lengthR满足lengthL lengthR 或 lengthL lengthR1的两个数组的划分点维护新左部分的最大值与新右部分的最小值判断是否满足新左部分的最大值小于或等于新右部分的最小值若满足则收缩左边界若不满足则收缩有边界直到找到最大的满足条件的ii为第一个数组的划分点最后根据两个数组的总长度的奇偶性来返回答案若总长度为奇数则答案为新左部分的最大值若总长度为偶数则答案为新左部分最大值与新右部分最小值之和的一半。其中还有很多分析和实现上的细节更具体的请参考官方题解方法二的分析总结本题的二分法不是常规思路需要很多的分析才能知道如何通过二分实现剪枝尤其要分析并结合中位数的特点来思考如何二分在限制时间复杂度为O(log (mn))的情况下本题较难想到解题思路。方法一将本题转化成寻找两个有序数组中的第 k 小的数其中 k 为 (mn)/2 或 (mn)/21。方法二将本题转化成在 [0,m] m一定满足mn中找到最大的 i使得A[i−1]≤B[j]其中 j(mn1)/2 - i 。