（1）4. 尋找兩個有序陣列的中位數（中）
https://leetcode-cn.com/problems/median-of-two-sorted-arrays/
給定兩個大小為 m 和 n 的有序陣列 nums1 和 nums2，
請你找出這兩個有序陣列的中位數，并且要求演算法的時間復雜度為 O(log(m + n))，
你可以假設 nums1 和 nums2 不會同時為空，
示例 1:
nums1 = [1, 3]
nums2 = [2]
則中位數是 2.0
示例 2:
nums1 = [1, 2]
nums2 = [3, 4]
則中位數是 (2 + 3)/2 = 2.5
思路：思路不是很難，但要注意很多邊界情況，詳情參考下面別人的注釋：
/* * 1.首先，讓我們在任一位置 i 將 A(長度為m) 劃分成兩個部分： * leftA | rightA * A[0],A[1],... A[i-1] | A[i],A[i+1],...A[m - 1] * * 由于A有m個元素，所以有m + 1中劃分方式(i = 0 ~ m) * * 我們知道len(leftA) = i, len(rightA) = m - i; * 注意：當i = 0時，leftA是空集，而當i = m時，rightA為空集， * * 2.采用同樣的方式，將B也劃分為兩部分： * leftB | rightB * B[0],B[1],... B[j-1] | B[j],B[j+1],...B[n - 1] * 我們知道len(leftA) = j, len(rightA) = n - j; * * 將leftA和leftB放入一個集合，將rightA和rightB放入一個集合，再把這兩個集合分別命名為leftPart和rightPart， * * leftPart | rightPart * A[0],A[1],... A[i-1] | A[i],A[i+1],...A[m - 1] * B[0],B[1],... B[j-1] | B[j],B[j+1],...B[n - 1] * * 如果我們可以確認： * 1.len(leftPart) = len(rightPart); =====> 該條件在m+n為奇數時，該推理不成立 * 2.max(leftPart) <= min(rightPart); * * median = (max(leftPart) + min(rightPart)) / 2; 目標結果 * * 要確保這兩個條件滿足： * 1.i + j = m - i + n - j(或m - i + n - j + 1) 如果n >= m，只需要使i = 0 ~ m，j = (m+n+1)/2-i =====> 該條件在m+n為奇數/偶數時，該推理都成立 * 2.B[j] >= A[i-1] 并且 A[i] >= B[j-1] * * 注意: * 1.臨界條件：i=0,j=0,i=m,j=n，需要考慮 * 2.為什么n >= m ? 由于0 <= i <= m且j = (m+n+1)/2-i,必須確保j不能為負數， * * 按照以下步驟進行二叉樹搜索 * 1.設imin = 0,imax = m，然后開始在[imin,imax]中進行搜索 * 2.令i = (imin+imax) / 2, j = (m+n+1)/2-i * 3.現在我們有len(leftPart) = len(rightPart)，而我們只會遇到三種情況： * * ①.B[j] >= A[i-1] 并且 A[i] >= B[j-1] 滿足條件 * ②.B[j-1] > A[i]，此時應該把i增大， 即imin = i + 1; * ③.A[i-1] > B[j]，此時應該把i減小， 即imax = i - 1; * * */
代碼：
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int m=nums1.length,n=nums2.length;
if(m>n){
int []tmp=nums1;nums1=nums2;nums2=tmp;
int t=m;m=n;n=t;
}
int l=0,r=m,i,midNum=(m+n+1)/2;
while(l<=r){
i=(l+r)>>1;
int j=midNum-i;
if(i-1>=0&&j<n&&nums1[i-1]>nums2[j]){
r=i-1;
}else if(j-1>=0&&i<m&&nums2[j-1]>nums1[i]){
l=i+1;
}else {
int mx,mn;
if(i==0){
mx=nums2[j-1];
}else if(j==0){
mx=nums1[i-1];
}else
mx=Math.max(nums1[i-1],nums2[j-1]);
if((m+n)%2==1)
return mx;
if(i==m){
mn=nums2[j];
}else if(j==n){
mn=nums1[i];
}else
mn=Math.min(nums1[i],nums2[j]);
return (mn+mx)*1.0/2;
}
}
return 0;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/114560.html
標籤：其他