題目
給定兩個大小為 m 和 n 的正序（從小到大）數(shù)組 nums1 和 nums2婉称。
請你找出這兩個正序數(shù)組的中位數(shù)监徘，并且要求算法的時間復(fù)雜度為 O(log(m + n))。
你可以假設(shè) nums1 和 nums2 不會同時為空详瑞。
樣例輸入輸出
nums1 = [1, 3]
nums2 = [2]
則中位數(shù)是 2.0
nums1 = [1, 2]
nums2 = [3, 4]
則中位數(shù)是 (2 + 3)/2 = 2.5
解題思路
這里給出的思路是本渣渣的普通人第一反應(yīng)思路请毛。
首先我們理解題目中說的中位數(shù)，中位數(shù)就是簡單點說就是一個可以數(shù)組中分割成兩部分聂薪，一辦大于它家乘，一半小于它。所以它在數(shù)組中的位置一般都是在中間的位置藏澳。
好了我們已經(jīng)知道了中位數(shù)的概念仁锯，如果求一個數(shù)組中的中位數(shù)，我們就可以很容易的求出來翔悠。直接求中間的下標(biāo)就行业崖。那么題目中是兩個數(shù)組呢野芒？我們正常人的思維呢就是合并一個數(shù)組，然后求中間的下標(biāo)就行双炕。但是合并數(shù)組的復(fù)雜度太大狞悲，我們可以只合并到中位數(shù)的位置就行，因為我們只要中位數(shù)妇斤。
這里合并我們需要一點摇锋，就是奇偶數(shù)的情況。如果我們的數(shù)組總長度是奇數(shù)的話站超，那么中位數(shù)就是中間的位置荸恕，如果是偶數(shù)的話，我們就是最中間兩個數(shù)的和除以2死相。所以我們應(yīng)該在結(jié)果的時候分情況處理融求。而在中間記錄中位數(shù)的時候，我們要記錄兩個數(shù)媳纬，一個是奇數(shù)的中位數(shù)双肤，同時也是偶數(shù)那兩個數(shù)中較大的那一個數(shù)，所以我們同時還要再記錄一個偶數(shù)那兩個較小的數(shù)钮惠。下面直接貼具體的代碼茅糜，注釋也會解釋的。
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int len1 = nums1.length,len2 = nums2.length;
int lens = len1 + len2;
//奇數(shù)情況中位數(shù)在位置素挽，偶數(shù)情況兩個數(shù)較大的那一個數(shù)所在的位置
int resMedian = (lens) / 2;
//用來進行兩個數(shù)組滑動的指針
int i = 0, j = 0;
//中位數(shù)（numMedian2）和偶數(shù)較小的那一個數(shù)（numMedian1）
double numMedian1 = 0,numMedian2 = 0;
while(i < len1 || j < len2){
if(i < len1 && j < len2){
//兩個數(shù)組都還有數(shù)
if(nums1[i] < nums2[j]){
//兩個指針的位置加起來等于我們合并數(shù)組中偶數(shù)較小的那一個數(shù)的位置
if(i + j == resMedian - 1) numMedian1 = nums1[i];
//兩個兩個指針的位置加起來等于我們合并數(shù)組中奇數(shù)要的那個中位數(shù)位置
if(i + j == resMedian) numMedian2 = nums1[i];
++i;
}else{
if(i + j == resMedian - 1) numMedian1 = nums2[j];
if(i + j == resMedian) numMedian2 = nums2[j];
++j;
}
//只有nums2還有數(shù)
}else if(j < len2){
if(i + j == resMedian - 1) numMedian1 = nums2[j];
if(i + j == resMedian) numMedian2 = nums2[j];
++j;
//只有nums1還有數(shù)
}else if(i < len1){
if(i + j == resMedian - 1) numMedian1 = nums1[i];
if(i + j == resMedian) numMedian2 = nums1[i];
++i;
}
}
//如果中位數(shù)是兩個數(shù)之和除以2的情況
if(lens % 2 == 0){
return (numMedian1 + numMedian2) / 2;
//如果中位數(shù)直接是中間位置的情況
}else{
return numMedian2;
}
}
}
雖然代碼寫的有點啰嗦蔑赘，不過復(fù)雜度還行的。
