本篇內(nèi)容介紹了“如何實(shí)現(xiàn)尋找兩個(gè)正序數(shù)組的中位數(shù)”的有關(guān)知識(shí)，在實(shí)際案例的操作過程中，不少人都會(huì)遇到這樣的困境，接下來就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細(xì)閱讀，能夠?qū)W有所成！
創(chuàng)新互聯(lián)于2013年創(chuàng)立，先為長(zhǎng)豐等服務(wù)建站，長(zhǎng)豐等地企業(yè)，進(jìn)行企業(yè)商務(wù)咨詢服務(wù)。為長(zhǎng)豐企業(yè)網(wǎng)站制作PC+手機(jī)+微官網(wǎng)三網(wǎng)同步一站式服務(wù)解決您的所有建站問題。
難度：困難
給定兩個(gè)大小分別為 m 和 n 的正序（從小到大）數(shù)組 nums1 和 nums2。請(qǐng)你找出并返回這兩個(gè)正序數(shù)組的 中位數(shù)。
示例 1：
輸入：nums1 = [1,3], nums2 = [2] 輸出：2.00000 解釋：合并數(shù)組 = [1,2,3] ，中位數(shù) 2
示例 2：
輸入：nums1 = [1,2], nums2 = [3,4] 輸出：2.50000 解釋：合并數(shù)組 = [1,2,3,4] ，中位數(shù) (2 + 3) / 2 = 2.5
示例 3：
輸入：nums1 = [0,0], nums2 = [0,0] 輸出：0.00000
示例 4：
輸入：nums1 = [], nums2 = [1] 輸出：1.00000
示例 5：
輸入：nums1 = [2], nums2 = [] 輸出：2.00000
提示：
nums1.length == m nums2.length == n 0 <= m <= 1000 0 <= n <= 1000 1 <= m + n <= 2000 -106 <= nums1[i], nums2[i] <= 106
從題目中透露的細(xì)節(jié)要求
中位數(shù)
兩個(gè)集合
兩個(gè)集合均為正序集合
找出這兩個(gè)正序集合的中位數(shù)
什么是中位數(shù)
首先需要正確理解中位數(shù)的概念，中位數(shù)是指，一個(gè)集合中，處于中間的數(shù)的數(shù)字，如果集合的長(zhǎng)度為奇數(shù)，則為中間的數(shù)字，如果為偶數(shù)，則為中間兩個(gè)數(shù)的平均數(shù)
針對(duì)這道題，我們?cè)谟?jì)算中位數(shù)的時(shí)候需要區(qū)分最終的長(zhǎng)度，最終是奇數(shù)還是偶數(shù)
合并兩個(gè)正序集合
找出兩個(gè)正序集合的中位數(shù)，首先第一反應(yīng)想到的是合并兩個(gè)正序集合，合并兩個(gè)正序集合又帶來新的問題，保證排序后的新集合也是正序的，否則求出來的中位數(shù)的結(jié)果是不對(duì)的
合并兩個(gè)正序集合，簡(jiǎn)單粗暴的做法是，直接使用JDK現(xiàn)成的API合并兩個(gè)數(shù)組，并且進(jìn)行SORT排序，但是這樣會(huì)造成時(shí)間復(fù)雜度及空間復(fù)雜度增加，所以這里我們采用常見的雙指針的方式
雙指針
采用三個(gè)指針指向三個(gè)數(shù)組數(shù)組的當(dāng)前下標(biāo)，默認(rèn)從0開始，判斷兩個(gè)老數(shù)組的初始坐標(biāo)值，小的數(shù)據(jù)則放入到新的數(shù)組中，并且更新對(duì)應(yīng)的下標(biāo)，如下圖所示，A[0] < B[0] ，將A[0]的值賦值給C，C[0]=0 ,并且將C的坐標(biāo)自增，同時(shí)A的值比較小，所以A的下標(biāo)自增，B坐標(biāo)不動(dòng)，如此循環(huán)
當(dāng)A的坐標(biāo)，或B的坐標(biāo)等于對(duì)應(yīng)的數(shù)組集合長(zhǎng)度時(shí)，說明對(duì)應(yīng)的數(shù)組集合已經(jīng)遍歷完了，我們則可以直接拼接對(duì)應(yīng)另外一個(gè)集合到新的集合中即可，直到最終兩個(gè)集合拼接完成
拼接新的集合完成之后，判斷最終集合的長(zhǎng)度為奇數(shù)還是偶數(shù)，最終取出中位數(shù)，返回即可
但其實(shí)我們也可以不需要完全合并兩個(gè)有序數(shù)組，只要找到中位數(shù)的位置即可，由于兩個(gè)數(shù)組的長(zhǎng)度已知，因此中位數(shù)對(duì)應(yīng)的兩個(gè)數(shù)組的下標(biāo)之和也是已知的。在每次賦值完C之后，判斷當(dāng)前C下標(biāo)的值是否為中位數(shù)位置，如果是可直接計(jì)算中位數(shù)的值返回即可，整理的時(shí)間復(fù)雜度也會(huì)縮短一半
這里強(qiáng)調(diào)一點(diǎn)，必須要賦值完C，因?yàn)槿绻扰袛嘀形粩?shù)，則C還沒有賦值完，最終的結(jié)果肯定是不對(duì)的
重慶分公司
重慶分公司
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int length2= nums1.length ;
int length3= nums2.length ;
int lengthSum = length2+length3;
//是否偶數(shù)
boolean type ;
int half =0;;
//偶數(shù)
if(lengthSum%2 == 0){
// half , half+1 8/2-1=4-1=3 [0,1,2,3,4,5,6,7]
half = lengthSum/2-1;
type= true;
}else{
//奇數(shù) 7/2=3
half = lengthSum/2;
type= false;
}
// num1下標(biāo)
int a = 0 ;
// num2下標(biāo)
int b = 0 ;
// newnums下標(biāo)
int c = 0 ;
int[] newnums = new int[lengthSum];
while(true){
//a已經(jīng)遍歷完了
if(a==length2){
newnums[c] = nums2[b];
b++;
//半數(shù)
if(c==half&&!type){
return newnums[c]/1.0;
}
if(c==(half+1)&&type){
return (newnums[c]+newnums[c-1])/2.0;
}
c++;
continue ;
}
//b已經(jīng)遍歷完了
if(b==length3){
newnums[c] = nums1[a];
a++;
//半數(shù)
if(c==half&&!type){
return newnums[c]/1.0;
}
if(c==(half+1)&&type){
return (newnums[c]+newnums[c-1])/2.0;
}
c++;
continue ;
}
if(nums1[a] >= nums2[b]){
newnums[c] = nums2[b];
b++;
}else{
newnums[c] = nums1[a];
a++;
}
//半數(shù)
if(c==half&&!type){
return newnums[c]/1.0;
}
if(c==(half+1)&&type){
return (newnums[c]+newnums[c-1])/2.0;
}
c++;
}
}
}時(shí)間復(fù)雜度：O(m+n)，最長(zhǎng)可能需要完全遍歷兩個(gè)數(shù)組
空間復(fù)雜度：O(1)
執(zhí)行用時(shí)：3 ms, 在所有 Java 提交中擊敗了82.60%的用戶
內(nèi)存消耗：39.7 MB, 在所有 Java 提交中擊敗了63.95%的用戶
我曾在銀色平原漫步,也曾在青草之河垂釣，這片土地認(rèn)識(shí)我，我們?nèi)舨粓?jiān)強(qiáng)，就將滅亡
“如何實(shí)現(xiàn)尋找兩個(gè)正序數(shù)組的中位數(shù)”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識(shí)可以關(guān)注創(chuàng)新互聯(lián)網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實(shí)用文章！
