描述
兩個(gè)排序的數(shù)組A和B幅虑，分別含有m和n個(gè)數(shù)微渠，找到兩個(gè)排序數(shù)組的中位數(shù)漏峰，要求時(shí)間復(fù)雜度應(yīng)為O(log (m+n))
樣例
給出數(shù)組A = [1,2,3,4,5,6] B = [2,3,4,5]睛廊，中位數(shù)3.5
給出數(shù)組A = [1,2,3] B = [4,5]调卑，中位數(shù) 3
時(shí)間復(fù)雜度為O(log n)
思路
根據(jù)時(shí)間復(fù)雜度尋找算法，所謂logk的時(shí)間復(fù)雜度就是在O(1)的時(shí)間使得規(guī)模為n的問(wèn)題變?yōu)閚/2;
通過(guò)比較兩個(gè)數(shù)組k/2位置的值大小丟掉值較小一個(gè)數(shù)組中k/2個(gè)數(shù)
代碼
public class Solution {
/*
* @param A: An integer array
* @param B: An integer array
* @return: a double whose format is *.5 or *.0
*/
public double findMedianSortedArrays(int[] A, int[] B) {
int len = A.length + B.length;
if (len % 2 == 1) {
return findKth(A, 0, B, 0, len / 2 + 1);
} else {
return (findKth(A, 0, B, 0, len / 2) + findKth(A, 0, B, 0, len / 2 + 1)) / 2.0;
}
}
// k 是整個(gè)排序數(shù)組(兩個(gè)數(shù)組合并后)的中位數(shù)
public static int findKth(int[] A,
int A_startIndex,
int[] B,
int B_startIndex,
int k) {
// 各種異常情況
// A 數(shù)組最后一個(gè)下標(biāo)是 A.length - 1;
if (A_startIndex >= A.length) {
return B[B_startIndex + k - 1];
}
if (B_startIndex >= B.length) {
return A[A_startIndex + k - 1];
}
// 遞歸出口
if (k == 1) {
return Math.min(A[A_startIndex], B[B_startIndex]);
}
// 比較A數(shù)組和B數(shù)組的第k/2個(gè)數(shù)的大小,哪個(gè)小把哪個(gè)數(shù)組的前k/2個(gè)數(shù)拋掉
int A_key = Integer.MAX_VALUE;
int B_key = Integer.MAX_VALUE;
if (A_startIndex + k / 2 - 1 < A.length) {
A_key = A[A_startIndex + k / 2 - 1];
}
if (B_startIndex + k / 2 - 1 < B.length) {
B_key = B[B_startIndex + k / 2 - 1];
}
// 拋掉k/2個(gè)數(shù),通過(guò)O(1)的操作使問(wèn)題的規(guī)模減小一半
if (A_key < B_key) {
return findKth(A, A_startIndex + k / 2, B, B_startIndex, k - k / 2 );
} else {
return findKth(A, A_startIndex, B, B_startIndex + k / 2, k - k / 2);
}
}
}
