二分法分页 mysql_LeetCode 04寻找两个正序数组的中位数(困难)二分法
嘔心瀝血的一個題解，點贊關注在看，一鍵三聯，一起加入我們打卡！。
題目描述：嘔心瀝血的一個題解，點贊關注收藏，一鍵三聯，一起加入我們打卡！
題目描述：給定兩個大小為 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
歸并法(O(m+n))
分析之前小吐槽一句，這題自己真的沒想到O(log(m+n))的方法，只能想到O(m+n)的歸并，沒想到怎么去使用二分，后來看了題解也是才明白。但也算自己理解了和大家分享一下。
對于這個問題或許本身不難，但是可能難在O(log(m+n))的時間復雜度上。
如果真的無法想到好的方法，先想著過關，該用什么方法呢？
法一暴力法：
可以將兩個數組添加到一個總的數組中，然后給這個數組進行排序。正常的排序是O(nlogn)的時間復雜度。排序之后根據奇數偶數取中位數即可。
法二歸并法：
給的兩個數組本身是有序的，想必熟悉歸并排序的朋友們應該能一下就想出來這個方法，兩個有序的.只需按照以下流程即可完成歸并：待歸并的兩個數組分別設置兩個指針leftindex，rightindex均從0開始。新數組也設置游標index。
比較兩數組leftindex和rightindex位置的值，較小的那個賦值到新數組中同時新數組游標和較小的那個游標均加一。在這里插入圖片描述
重復到其中一個數組遍歷完，另一個數組剩余值直接加入后面即可。在這里插入圖片描述
實現代碼：public?double?findMedianSortedArrays(int[]?nums1,?int[]?nums2){
int?a[]=new?int[nums1.length+nums2.length];
int?lindex=0,rindex=0;
int?index=0;
while?(lindex
if(nums1[lindex]
{
a[index++]=nums1[lindex++];
}
else?{
a[index++]=nums2[rindex++];
}
}
while?(lindex
a[index++]=nums1[lindex++];
}
while?(rindex
a[index++]=nums2[rindex++];
}
if(a.length%2==0)
return?(double)(a[a.length/2-1]+a[a.length/2])/2;
else?{
return?a[a.length/2];
}
}
二分法(O(log(m+n)))
想到有序的，又是O(log(m+n))的時間復雜度，估計大部分人都能想到二分，我當時也是一樣，但是該怎么想呢這就是一個問題。記錄下我當初錯誤的想法：二分，二分找到兩個中間的。然后正常有個長的，有個短的，根據兩個數值比較分類推測中位數應該在哪個區間……然后大腦就斷電了。
對于中位數的簡單分析：如果兩個數組長度和為奇數，那么最終這個中位數是由一位數確定的。
如果兩個數組長度和為偶數，那么最終這個中位數是由兩位數取平均值確定的。
對兩個數組的簡單分析：兩個數組應該有一個長一點，另一個點一點(等長也不影響)。
中位數可能讓兩個數組都分成兩部分：一部分小于中位數，一部分大于中位數。但兩個部分合起來總數量應該一致。
在這里插入圖片描述
對兩數組和中位數位置分析：我們知道兩數組雖然可能等長(不影響)，但正常情況應該是一個長(m)一個短(n)。長短數組分別對應的坐標m1和n1和中位數坐標有什么關系？
無論總和奇數偶數，都滿足(m1+n1)=(m+n)/2;因為兩個數組都是有序的所以總共小于中位數的占一半。其中m和n是定值。也就是不管你怎么變動，這兩個坐標編號是總和為定值得！
如何分析為定值得坐標既然兩個坐標的總和為定值，那么可不可以把其中一個當為自變量，一個看成自變量呢？比如x+y=5你不好分析但是y=5-x，你分析x同時y就確定了。對吧？
那么選擇長的那個作為變量還是短的那個作為變量呢？短的，為啥，主要因為如果從長的當成變量咱們有些區域無法對應到短的(因為長度即使加上短的所有也到不了一半，處理起來麻煩)：
在這里插入圖片描述
但是短的就可以很好避免這種情況：
在這里插入圖片描述
所以我們就用二分去查找小的這個區間，找到最終的結果，你可能會問：什么樣情況能夠滿足確定這條線的附近就是產生中位數的？二分進行查找編號的時候，滿足左側都比線右側小才行。這種情況在二分查找就是一個平衡的結果。
在這里插入圖片描述
最后找到這個index線了。取值比較你還要有注意的地方：取左側的時候左側如果有index為0，取右側的時候index為最大值：
在這里插入圖片描述
所以這種在你最后取值的時候，需要考慮左右側是否有值。同時取長的那個也要比較，因為可能出現等長情況例如：1 2 3 4,和5 6 7 8這種去到臨界。需要判斷當然在實現過程用三目運算簡化！
總的來說：根據短的進行二分查找位置，先找到線index，說明中位數在附近產生。(奇數偶數在查找因為要除2可以通用表達式)
如果總個數奇數，那么就是線左側最大的那個(兩個比較或只有一個)
如果總個數偶數，那么就是線左側最大的那個(兩個比較或只有一個)和線右側最小的那個(兩個比較或只有一個)的值取平均，注意是double類型。
其他注意點，搞清index從0開始，搞清邏輯上的第幾個和數組顯示使用的第幾個的index的區別。
附上代碼：public?static?double?findMedianSortedArrays2(int[]?nums1,?int[]?nums2){
if(nums1.length>nums2.length)//保證num1長度小，如果不小我交換一下
{
int?team[]=nums2.clone();
nums2=nums1;
nums1=team;
}
int?k=(nums1.length+nums2.length+1)/2;//理論中位數滿足的位置
int?left=0,right=nums1.length;//二分查找短的
while?(left
int?m1=(left+right)/2;//在短的位置
int?m2=k-m1;//在長的第幾個
//System.out.println(m1+"?"+m2);
if(nums1[m1]
left=m1+1;
else?{//right左移
right=m1;
}
}
//System.out.println(left+"?"+k);
//左側最大和右側最小那個先算出來再說，根據奇偶再使用
double?leftbig=?Math.max(left==0?Integer.MIN_VALUE:nums1[left-1],?k-left==0?Integer.MIN_VALUE:nums2[k-left-1]);
double?rightsmall=Math.min(left==nums1.length?Integer.MAX_VALUE:nums1[left],k-left==nums2.length?Integer.MAX_VALUE:nums2[k-left]);
//System.out.println(rightsmall);
if((nums1.length+nums2.length)%2==0)
{
return?(leftbig+rightsmall)/2;
}
else?{
return?leftbig;
}
}
結語
本次打卡結束，再接再勵。
至于其他方法暫時先不學了，感覺這題還是挺有難度的，需要搞明白要點時候。
總結
以上是生活随笔為你收集整理的二分法分页 mysql_LeetCode 04寻找两个正序数组的中位数(困难)二分法的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： python编写查询_如何用python
- 下一篇： java多线程爬虫_Java 多线程爬虫