Description
There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
Example 1
nums1 = [1, 3]
nums2 = [2]
The median is 2.0
Example 2
nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5
初始分析: O(m+n)
首先，分析題目要求膜廊，該函數(shù)：輸入?yún)?shù)為兩個(gè)有序數(shù)組栈暇，輸出要求為這兩個(gè)數(shù)組內(nèi)所有數(shù)字集的中位數(shù)。
*額外要求：算法的時(shí)間復(fù)雜度小于等于 O(log (m+n)).
先撇開額外要求不談茁裙，碰到兩個(gè)有序數(shù)組的合并硫眨，我首先想到的是歸并排序(Merge Sort)的思想渊抄。歸并排序本身就是不斷遞歸地分割原始數(shù)組再進(jìn)行子數(shù)組排序尝胆，最后合并這些有序子數(shù)組。而此處我只需要做有序數(shù)組的合并护桦。
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int[] sorted = mergeSort(nums1, nums2);
if((sorted.length&1)==1){
return sorted[sorted.length/2];
}else{
return (sorted[sorted.length/2 - 1] + sorted[sorted.length/2])/2.0;
}
}
public int[] mergeSort(int[] a, int[] b){
int[] output = new int[a.length + b.length];
int lt = 0;
int rt = 0;
int index = 0;
while(lt<a.length && rt<b.length){
if(a[lt]<b[rt]){
output[index++] = a[lt++];
}else{
output[index++] = b[rt++];
}
}
if(lt!=a.length){
System.arraycopy(a, lt, output, lt+rt, a.length-lt);
}else{
System.arraycopy(b, rt, output, lt+rt, b.length-rt);
}
return output;
}
}
基于這個(gè)想法的代碼大概長這樣(有可以改進(jìn)的地方歡迎提出)含衔。
時(shí)間復(fù)雜度為O(m+n)，能被AC，打敗了40%的java算法贪染。
深度分析: O(log(min(m,n)))缓呛，思路參考LeetCode網(wǎng)友MissMary
首先理解中位數(shù)的代數(shù)意義：
中位數(shù), 統(tǒng)計(jì)學(xué)中的專有名詞，代表一個(gè)樣本杭隙、種群或概率分布中的一個(gè)數(shù)值哟绊，其可 將數(shù)值集合劃分為長度相等的上下兩部分。
關(guān)鍵在于后半句： 將數(shù)值集合劃分為長度相等的上下兩部分
除此之外痰憎，對于劃分后的兩組數(shù)字票髓，其中一組內(nèi)的數(shù)字總是大于另一組內(nèi)的數(shù)字。
舉個(gè)例子铣耘，先把第一個(gè)數(shù)組（稱為數(shù)組A）在隨機(jī)位置 i 處分割開：
| 左半邊 | 右半邊 |
|---|---|
| A[0], A[1],....,A[i-1] | A[i], A[i+1],...,A[m-1] |
同樣地洽沟，在隨機(jī)位置 j 處 將數(shù)組B分割開：
| 左半邊 | 右半邊 |
|---|---|
| B[0], B[1],....,B[j-1] | B[j], B[j+1],...,B[n-1] |
將A、B數(shù)組的左半邊放到一起蜗细，右半邊放到一起裆操， 可得：
| 左半邊 | 右半邊 |
|---|---|
| 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] |
如果這樣的分組能滿足下面兩個(gè)條件：
1. len(左半邊)==len(右半邊)
2. max(左半邊)<=min(右半邊)
就說明我們就成功的將{A,B}中的所有元素分割成了等長的兩部分，且左半邊的數(shù)字總小于右半邊的數(shù)字炉媒。
這時(shí)踪区，中位數(shù)可以很輕易地通過 Median = (max(左半邊)+min(右半邊))/2 計(jì)算出來。
為了滿足這兩個(gè)條件吊骤，我們只需要保證：
1). 左右兩部分等長：
i + j == m - i + n - j (或者: m - i + n - j + 1)
假設(shè) n >= m, 只需要讓: i = 0 ~ m, j = (m + n + 1)/2 - i
2). B[j-1] <= A[i] and A[i-1] <= B[j]
為什么需要假設(shè)n>=m朽缴？ 因?yàn)槿绻鹠>n， 則B數(shù)組的下標(biāo)索引 j 有可能變成負(fù)數(shù)水援。
對于 i 和 j 等于0的邊緣情況，留到后面討論
所以茅郎，簡而言之蜗元，程序需要做的僅僅是：
在[0, m]中尋找合適的分割點(diǎn) i , 使得:
B[j-1] <= A[i] and A[i-1] <= B[j], ( 其中 j = (m + n + 1)/2 - i )
這個(gè)過程可以通過二分查找法提高效率：
<1> 設(shè) imin = 0, imax = m, 然后在 [imin, imax] 中進(jìn)行查找
<2> 設(shè) i = (imin + imax)/2, j = (m + n + 1)/2 - i
<3> 接下來有三種情況:
<a> B[j-1] <= A[i] and A[i-1] <= B[j]
//找到了合適的分割點(diǎn) i， 停止搜索
<b> B[j-1] > A[i]
//A[i] 的值偏小. 需要調(diào)整 i 使得 `B[j-1] <= A[i]`.
//此處應(yīng)該增大 i 值系冗，因?yàn)楫?dāng) i 值增大時(shí), j 值會(huì)減小.
//因此B[j-1]會(huì)隨A[i]的增大而減小, 更容易滿足 `B[j-1] <= A[i]`
//所以應(yīng)將搜索范圍調(diào)整為 [i+1, imax]. 即: 使 imin = i+1, 然后回到步驟 <2>.
<c> A[i-1] > B[j]
//與前一種情況的處理方式相反奕扣，即: 使 imax = i-1，然后回到步驟<2>.
當(dāng)找到合適的分割點(diǎn) i 后掌敬，易知中位數(shù)為：
當(dāng) m + n 為奇數(shù)：max(A[i-1], B[j-1])
當(dāng) m + n 為偶數(shù)：(max(A[i-1], B[j-1]) + min(A[i], B[j]))/2
再來考慮邊緣情況惯豆，即： 當(dāng) i=0,i=m,j=0,j=n 時(shí) A[i-1],B[j-1],A[i],B[j] 有可能不存在的情況：
其實(shí)這些情況非常容易分析，因?yàn)槲覀兯獫M足的僅僅是 max(左半邊) <= min(右半邊) 這個(gè)條件奔害，假設(shè)A[i-1],B[j-1],A[i],B[j]都存在楷兽，則該條件可表示為 B[j-1] <= A[i] and A[i-1] <= B[j]。如果有些值不存在的話則完全不用去判斷华临，比如我們假設(shè) i=0芯杀， 則 A[i-1]不存在，我們便不用判斷 A[i-1] <= B[j]這個(gè)條件，因?yàn)榇藭r(shí)數(shù)組A不存在左半邊揭厚。所以却特，考慮邊緣情況后，搜索思路大致為：
在 [0, m] 中尋找合適的分割點(diǎn) i筛圆， 使得:
(j == 0 or i == m or B[j-1] <= A[i]) and
(i == 0 or j == n or A[i-1] <= B[j])裂明，
其中 j = (m + n + 1)/2 - i
在搜索的過程中，會(huì)出現(xiàn)下面三種情況：
<a> (j == 0 or i == m or B[j-1] <= A[i]) and
(i == 0 or j = n or A[i-1] <= B[j])
//找到合適的 i 值太援，停止搜索
<b> j > 0 and i < m and B[j - 1] > A[i]
// i 值偏小闽晦，需要增加 i 值
<c> i > 0 and j < n and A[i - 1] > B[j]
// i 值偏大，需要減小 i 值
其中<b>和<c>的判斷條件可以進(jìn)一步簡化為
<b> i < m and B[j - 1] > A[i]
<c> i > 0 and A[i - 1] > B[j]
因?yàn)楫?dāng) i < m時(shí)粉寞，j一定大于0尼荆，且 i>0 時(shí)，j一定小于n唧垦，推導(dǎo)過程為：
m <= n, i < m ==> j = (m+n+1)/2 - i > (m+n+1)/2 - m >= (2*m+1)/2 - m >= 0
m <= n, i > 0 ==> j = (m+n+1)/2 - i < (m+n+1)/2 <= (2*n+1)/2 <= n
基于上述的思路的Java代碼如下：
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2)
{
int m = nums1.length;
int n = nums2.length;
if(m>n)
{
int[] tmp = nums1;
nums1 = nums2;
nums2 = tmp;
m=m^n;
n=m^n;
m=m^n;
} //交換m與n的值捅儒，以及nums1和nums2的引用
int imin = 0;
int imax = m;
int half = (m+n+1)>>1;
while(imin<=imax)
{
int i = (imin + imax)>>1;
int j = half - i;
if(i<m && nums2[j-1]>nums1[i])
imin = ++i; //i值偏小
else if(i>0 && nums1[i-1]>nums2[j])
imax = --i; //i值偏大
else //完美情況
{
int max_left = 0;
if(i==0)
max_left = nums2[j-1];
else if(j==0)
max_left = nums1[i-1];
else
max_left = Math.max(nums1[i-1], nums2[j-1]);
if(((m+n)&1)==1)
return max_left; //m+n為奇數(shù)的情況中位數(shù)為max_left
int min_right = 0;
if(i==m)
min_right = nums2[j];
else if(j==n)
min_right = nums1[i];
else
min_right = Math.min(nums1[i], nums2[j]);
return (max_left+min_right)/2.0; //m+n為偶數(shù)的情況中位數(shù)為(max_left+min_right)/2
}
}
return -1;
}
}
上述算法的時(shí)間復(fù)雜度為O(log(min(m,n))), 代碼部分有可以改進(jìn)的地方歡迎提出。
