1.題目描述
給定兩個(gè)大小為 m 和 n 的有序數(shù)組 nums1 和 nums2。
請(qǐng)你找出這兩個(gè)有序數(shù)組的中位數(shù)，并且要求算法的時(shí)間復(fù)雜度為 O(log(m + n))。
假設(shè) nums1 和 nums2 不會(huì)同時(shí)為空。
示例 1:
nums1 = [1, 3]
nums2 = [2]
則中位數(shù)是 2.0
示例 2:
nums1 = [1, 2]
nums2 = [3, 4]
則中位數(shù)是 (2 + 3)/2 = 2.5
2.思路分析
1.首先求中位數(shù)：如果是奇數(shù)：k/2+1,如果是偶數(shù)：(k/2+k/2+1)/2。數(shù)組從零開(kāi)始所以要往前移一位，且要以float類型輸出。
2.最先想到的方法：歸并排序？排成一個(gè)有序的數(shù)組，從而求得。
時(shí)間復(fù)雜度：遍歷全部數(shù)組 O(m+n)
空間復(fù)雜度：開(kāi)辟了一個(gè)數(shù)組，保存合并后的兩個(gè)數(shù)組 O(m+n)
3.時(shí)間復(fù)雜度都達(dá)不到題目的要求 O(log(m+n)。看到 log，很明顯，我們只有用到二分的方法才能達(dá)到。我們不妨用另一種思路，題目是求中位數(shù)，其實(shí)就是求第(m+n)/2小數(shù)的一種特殊情況。
=====>求兩個(gè)有序數(shù)組的第K個(gè)數(shù)
如圖兩個(gè)數(shù)組，假設(shè)我們要找第 7 小的數(shù)字。
我們比較兩個(gè)數(shù)組的第 k/2 個(gè)數(shù)字，如果 k 是奇數(shù)，向下取整。也就是比較第 3個(gè)數(shù)字，上邊數(shù)組中的 4和下邊數(shù)組中的3，如果哪個(gè)小，就表明該數(shù)組的前 k/2 個(gè)數(shù)字都不是第 k 小數(shù)字，所以可以排除。也就是 1，2，3 這三個(gè)數(shù)字不可能是第 7 小的數(shù)字，我們可以把它排除掉。將 1349和 45678910 兩個(gè)數(shù)組作為新的數(shù)組進(jìn)行比較。
依次遞歸~
出口的條件是：
①有一個(gè)數(shù)組為空
②所求得第k個(gè)值為1，則返回兩個(gè)數(shù)組最小的元素
3.代碼實(shí)現(xiàn)
暴力：歸并排序
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int[] nums;
int m = nums1.length;
int n = nums2.length;
nums = new int[m + n];
if (m == 0) {
if (n % 2 == 0) {
return (nums2[n / 2 - 1] + nums2[n / 2]) / 2.0;
} else {
return nums2[n / 2];
}
}
if (n == 0) {
if (m % 2 == 0) {
return (nums1[m / 2 - 1] + nums1[m / 2]) / 2.0;
} else {
return nums1[m / 2];
}
}
int count = 0;
int i = 0, j = 0;
while (count != (m + n)) {
if (i == m) {
while (j != n) {
nums[count++] = nums2[j++];
}
break;
}
if (j == n) {
while (i != m) {
nums[count++] = nums1[i++];
}
break;
}
if (nums1[i] < nums2[j]) {
nums[count++] = nums1[i++];
} else {
nums[count++] = nums2[j++];
}
}
if (count % 2 == 0) {
return (nums[count / 2 - 1] + nums[count / 2]) / 2.0;
} else {
return nums[count / 2];
}
}
二分法
public float findMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.length;
int n = nums2.length;
// 處理任何一個(gè)nums為空數(shù)組的情況
if (m == 0) {
if (n % 2 != 0)
return 1.0 * nums2[n / 2];
return (nums2[n / 2] + nums2[n / 2 - 1]) / 2.0;
}
if (n == 0) {
if (m % 2 != 0)
return 1.0 * nums1[m / 2];
return (nums1[m / 2] + nums1[m / 2 - 1]) / 2.0;
}
int total = m + n;
// 總數(shù)為奇數(shù)，找第 total / 2 + 1 個(gè)數(shù)
if ((total & 1) == 1) {
return find_kth(nums1, 0, nums2, 0, total / 2 + 1);
}
// 總數(shù)為偶數(shù)，找第 total / 2 個(gè)數(shù)和第total / 2 + 1個(gè)數(shù)的平均值
return (find_kth(nums1, 0, nums2, 0, total / 2) + find_kth(nums1, 0, nums2, 0, total / 2 + 1)) / 2.0;
}
// 尋找a 和 b 數(shù)組中，第k個(gè)數(shù)字
float find_kth(int[] a, int a_begin, int[] b, int b_begin, int k) {
// 當(dāng)a 或 b 超過(guò)數(shù)組長(zhǎng)度，則第k個(gè)數(shù)為另外一個(gè)數(shù)組第k個(gè)數(shù)
if (a_begin >= a.length)
return b[b_begin + k - 1];
if (b_begin >= b.length)
return a[a_begin + k - 1];
// k為1時(shí)，兩數(shù)組最小的那個(gè)為第一個(gè)數(shù)
if (k == 1)
return Math.min(a[a_begin], b[b_begin]);
int mid_a = Integer.MAX_VALUE;
int mid_b = Integer.MAX_VALUE;
// mid_a / mid_b 分別表示 a數(shù)組、b數(shù)組中第 k / 2 個(gè)數(shù)
if (a_begin + k / 2 - 1 < a.length)
mid_a = a[a_begin + k / 2 - 1];
if (b_begin + k / 2 - 1 < b.length)
mid_b = b[b_begin + k / 2 - 1];
// 如果a數(shù)組的第 k / 2 個(gè)數(shù)小于b數(shù)組的第 k / 2 個(gè)數(shù)，表示總的第 k 個(gè)數(shù)位于 a的第k / 2個(gè)數(shù)的后半段，或者是b的第 k
// / 2個(gè)數(shù)的前半段
// 由于范圍縮小了 k / 2 個(gè)數(shù)，此時(shí)總的第 k 個(gè)數(shù)實(shí)際上等于新的范圍內(nèi)的第 k - k / 2個(gè)數(shù)，依次遞歸
if (mid_a < mid_b)
//這里第二次遞歸時(shí)，k=k-k/2;不能是k=k/2,因?yàn)槲覀冎皇桥懦懊娴膋/2個(gè)
return find_kth(a, a_begin + k / 2, b, b_begin, k - k / 2);
// 否則相反
return find_kth(a, a_begin, b, b_begin + k / 2, k - k / 2);
}
