題目

標題和出處

標題：尋找兩個正序數組的中位數

出處：4. 尋找兩個正序數組的中位數

難度

8 級

題目描述

要求

給定兩個大小分別為 $\text{m}$ 和 $\text{n}$ 的升序數組 $\text{nums1}$ 和 $\text{nums2}$，返回這兩個升序數組的中位數。

要求時間復雜度是 $\text{O(log?(m?+?n))}$。

示例

示例 1：

輸入：$\text{nums1?=?[1,3],?nums2?=?[2]}$
輸出：$\text{2.00000}$
解釋：合并數組是 $\text{[1,2,3]}$，中位數是 $\text{2}$。

示例 2：

輸入：$\text{nums1?=?[1,2],?nums2?=?[3,4]}$
輸出：$\text{2.50000}$
解釋：合并數組是 $\text{[1,2,3,4]}$，中位數是 $\frac{\text{2}+\text{3}}{\text{2}}=\text{2.5}$。

數據范圍

• $\text{nums1.length}=\text{m}$
• $\text{nums2.length}=\text{n}$
• $\text{0}\le \text{m}\le \text{1000}$
• $\text{0}\le \text{n}\le \text{1000}$
• $\text{1}\le \text{m}+\text{n}\le \text{2000}$
• ${\text{-10}}^{\text{6}}\le \text{nums1[i],?nums2[i]}\le {\text{10}}^{\text{6}}$

解法一

思路和算法

已知兩個升序數組的長度分別是 $m$ 和 $n$。計算兩個升序數組的中位數可以轉換成找到兩個升序數組的所有元素中的第 $k$ 小元素，其中 $0\le k<m+n$。用 $\text{total}=m+n$ 表示兩個升序數組的長度之和。當 $\text{total}$ 是奇數時，$k=\frac{\text{total}?1}{2}$，第 $k$ 小元素即為中位數；當 $\text{total}$ 是偶數時，分別取 $k=\frac{\text{total}}{2}?1$ 和 $k=\frac{\text{total}}{2}$，兩次第 $k$ 小元素的平均數即為中位數。因此，根據兩個升序數組的長度之和是奇數或偶數，執(zhí)行一次或兩次尋找第 $k$ 小元素的操作，即可得到中位數。

由于題目要求時間復雜度是 $O(\log (m+n))$，因此要求每次尋找第 $k$ 小元素的操作的時間復雜度是 $O(\log (m+n))$。需要使用二分查找實現。

用 $k$ 表示目標值在剩余元素中的序號（$k$ 從 $0$ 開始，序號為 $k$ 表示剩余元素中有 $k$ 個元素小于等于目標值），用 ${\text{index}}_1$ 和 ${\text{index}}_2$ 分別表示數組 ${\text{nums}}_1$ 和 ${\text{nums}}_2$ 的首個剩余元素的下標，初始時 ${\text{index}}_1$ 和 ${\text{index}}_2$ 都等于 $0$。剩余元素表示可能是目標值的元素，查找過程中將不可能是目標值的元素排除。

每次查找時，分別考慮兩個數組的剩余元素中最小的 $?\frac{k}{2}?$ 個元素，共考慮 $k+1$ 個元素（當 $k$ 是奇數時）或 $k$ 個元素（當 $k$ 是偶數時），這些元素在兩個數組中的下標范圍分別是 ${\text{nums}}_1$ 的下標范圍 $[{\text{index}}_1,{\text{endIndex}}_1]$ 和 ${\text{nums}}_2$ 的下標范圍 $[{\text{index}}_2,{\text{endIndex}}_2]$，其中 ${\text{endIndex}}_1={\text{index}}_1+?\frac{k?1}{2}?$，${\text{endIndex}}_2={\text{index}}_2+?\frac{k?1}{2}?$。考慮 ${\text{nums}}_1[{\text{endIndex}}_1]$ 和 ${\text{nums}}_2[{\text{endIndex}}_2]$，其中的較大值是第 $k$ 小元素（當 $k$ 是奇數時）或第 $k?1$ 小元素（當 $k$ 是偶數時），因此其中的較小值一定不是第 $k$ 小元素。對于較小值所在的數組，可以將較小值以及較小值前面的元素全部排除。

需要注意的是，${\text{endIndex}}_1$ 和 ${\text{endIndex}}_2$ 不能超出數組下標范圍。如果一個數組的剩余元素個數少于 $?\frac{k}{2}?$，則該數組中考慮的元素是該數組中的全部剩余元素。因此有 ${\text{endIndex}}_1=\min ({\text{index}}_1+?\frac{k?1}{2}?,m?1)$，${\text{endIndex}}_2=\min ({\text{index}}_2+?\frac{k?1}{2}?,n?1)$。

由此可以根據三種情況分別做相應的處理，縮小查找范圍。

• 如果 ${\text{nums}}_1[{\text{endIndex}}_1]<{\text{nums}}_2[{\text{endIndex}}_2]$，則將 ${\text{nums}}_1$ 的下標范圍 $[{\text{index}}_1,{\text{endIndex}}_1]$ 中的元素全部排除，排除的元素個數是 ${\text{endIndex}}_1?{\text{index}}_1+1$。

• 如果 ${\text{nums}}_1[{\text{endIndex}}_1]>{\text{nums}}_2[{\text{endIndex}}_2]$，則將 ${\text{nums}}_2$ 的下標范圍 $[{\text{index}}_2,{\text{endIndex}}_2]$ 中的元素全部排除，排除的元素個數是 ${\text{endIndex}}_2?{\text{index}}_2+1$。

• 如果 ${\text{nums}}_1[{\text{endIndex}}_1]={\text{nums}}_2[{\text{endIndex}}_2]$，則處理方式和 ${\text{nums}}_1[{\text{endIndex}}_1]<{\text{nums}}_2[{\text{endIndex}}_2]$ 相同。

每次查找之后，將 $k$ 的值減去排除的元素個數，并將排除元素的數組的相應下標更新為該數組首個剩余元素的下標，具體做法如下：如果排除的是 ${\text{nums}}_1$ 中的元素，則將 ${\text{index}}_1$ 更新為 ${\text{endIndex}}_1+1$；如果排除的是 ${\text{nums}}_2$ 中的元素，則將 ${\text{index}}_2$ 更新為 ${\text{endIndex}}_2+1$。

二分查找的條件是 ${\text{index}}_1<m$，${\text{index}}_2<n$ 和 $k>0$。如果三個條件之一不滿足，則二分查找結束，得到目標值。

• 如果 ${\text{index}}_1=m$，則剩余元素都在 ${\text{nums}}_2$ 中，目標值是 ${\text{nums}}_2[{\text{index}}_2+k]$。

• 如果 ${\text{index}}_2=n$，則剩余元素都在 ${\text{nums}}_1$ 中，目標值是 ${\text{nums}}_1[{\text{index}}_1+k]$。

• 如果 $k=0$，則剩余元素中的最小元素是目標值，目標值是 $\min ({\text{nums}}_1[{\text{index}}_1],{\text{nums}}_2[{\text{index}}_2])$。

以下用一個例子說明該解法。

兩個數組是 ${\text{nums}}_1=[1,2,3,4,5]$，${\text{nums}}_2=[1,2,3,4,5,6,7,8,9,10]$，兩個數組的長度分別是 $m=5$，$n=10$，長度之和是 $15$，$k=7$。初始時，${\text{index}}_1=0$，${\text{index}}_2=0$。

1. 根據 ${\text{index}}_1=0$，${\text{index}}_2=0$ 和 $k=7$ 計算得到 ${\text{endIndex}}_1=3$，${\text{endIndex}}_2=3$。由于 ${\text{nums}}_1[3]={\text{nums}}_2[3]$，因此將 ${\text{nums}}_1$ 的下標范圍 $[0,3]$ 排除，排除 $4$ 個元素，更新得到 $k=3$，${\text{index}}_1=4$。

2. 根據 ${\text{index}}_1=4$，${\text{index}}_2=0$ 和 $k=3$ 計算得到 ${\text{endIndex}}_1=4$，${\text{endIndex}}_2=1$。由于 ${\text{nums}}_1[4]>{\text{nums}}_2[1]$，因此將 ${\text{nums}}_2$ 的下標范圍 $[0,1]$ 排除，排除 $2$ 個元素，更新得到 $k=1$，${\text{index}}_2=2$。

3. 根據 ${\text{index}}_1=4$，${\text{index}}_2=2$ 和 $k=1$ 計算得到 ${\text{endIndex}}_1=4$，${\text{endIndex}}_2=2$。由于 ${\text{nums}}_1[4]>{\text{nums}}_2[2]$，因此將 ${\text{nums}}_2$ 的下標范圍 $[2,2]$ 排除，排除 $1$ 個元素，更新得到 $k=0$，${\text{index}}_2=3$。

4. 此時 $k=0$，二分查找結束，${\text{nums}}_1[4]$ 和 ${\text{nums}}_2[3]$ 中的較小值 $4$ 即為目標值。

代碼

class Solution {public double findMedianSortedArrays(int[] nums1, int[] nums2) {int m = nums1.length, n = nums2.length;int total = m + n;if (total % 2 == 1) {int medianIndex = (total - 1) / 2;return findKthSmallest(medianIndex, nums1, nums2);} else {int medianIndex1 = total / 2 - 1, medianIndex2 = total / 2;return (findKthSmallest(medianIndex1, nums1, nums2) + findKthSmallest(medianIndex2, nums1, nums2)) / 2.0;}}public int findKthSmallest(int k, int[] nums1, int[] nums2) {int m = nums1.length, n = nums2.length;int index1 = 0, index2 = 0;while (index1 < m && index2 < n && k > 0) {int endIndex1 = Math.min(index1 + (k - 1) / 2, m - 1);int endIndex2 = Math.min(index2 + (k - 1) / 2, n - 1);int num1 = nums1[endIndex1], num2 = nums2[endIndex2];if (num1 <= num2) {k -= endIndex1 - index1 + 1;index1 = endIndex1 + 1;} else {k -= endIndex2 - index2 + 1;index2 = endIndex2 + 1;}}if (index1 == m) {return nums2[index2 + k];} else if (index2 == n) {return nums1[index1 + k];} else {return Math.min(nums1[index1], nums2[index2]);}}
}

復雜度分析

• 時間復雜度：$O(\log (m+n))$，其中 $m$ 和 $n$ 分別是數組 ${\text{nums}}_1$ 和 ${\text{nums}}_2$ 的長度。每次尋找第 $k$ 小元素時，$k$ 的初始值是 $m+n$ 的一半附近的整數，每次查找將 $k$ 的值減小一半，因此時間復雜度是 $O(\log (m+n))$。

• 空間復雜度：$O(1)$。

解法二

思路和算法

解法一的時間復雜度是 $O(\log (m+n))$，該時間復雜度已經很低，但是這道題還存在時間復雜度更低的解法。

為了找到中位數，需要在數組 ${\text{nums}}_1$ 和 ${\text{nums}}_2$ 中分別找到分割點 ${\text{cut}}_1$ 和 ${\text{cut}}_2$，將每個數組分割成兩個部分。

• 數組 ${\text{nums}}_1$ 被分割成下標范圍 $[0,{\text{cut}}_1?1]$ 和下標范圍 $[{\text{cut}}_1,m?1]$ 兩部分，左邊部分的長度是 ${\text{cut}}_1$。

• 數組 ${\text{nums}}_2$ 被分割成下標范圍 $[0,{\text{cut}}_2?1]$ 和下標范圍 $[{\text{cut}}_2,n?1]$ 兩部分，左邊部分的長度是 ${\text{cut}}_2$。

其中，$0\le {\text{cut}}_1\le m$，$0\le {\text{cut}}_2\le n$，即每個數組分割成的兩個部分中可以有一個部分為空。

假設 ${\text{nums}}_1[?1]={\text{nums}}_2[?1]=?\infty$，${\text{nums}}_1[m]={\text{nums}}_2[n]=+\infty$，分割應滿足以下兩個條件。

• 兩個數組的左邊部分的最大值小于等于兩個數組的右邊部分的最小值，$\max ({\text{nums}}_1[{\text{cut}}_1?1],{\text{nums}}_2[{\text{cut}}_2?1])\le \min ({\text{nums}}_1[{\text{cut}}_1],{\text{nums}}_2[{\text{cut}}_2])$。

• 兩個數組的左邊部分的長度之和為兩個數組的長度之和的一半向上取整，${\text{cut}}_1+{\text{cut}}_2=?\frac{m+n}{2}?$。

將兩個數組的左邊部分統稱為前半部分，將兩個數組的右邊部分統稱為后半部分，則前半部分的最大值小于等于后半部分的最小值，前半部分的元素個數為兩個數組的長度之和的一半向上取整。

用 $\text{total}=m+n$ 表示兩個升序數組的長度之和，用 $\text{lowerSize}=?\frac{\text{total}}{2}?$ 表示前半部分的元素個數。當 $\text{total}$ 是奇數時，中位數是前半部分的最大值；當 $\text{total}$ 是偶數時，中位數是前半部分的最大值與后半部分的最小值的平均數。

由于已知 ${\text{cut}}_1+{\text{cut}}_2=\text{lowerSize}$，因此可以在 ${\text{nums}}_1$ 中尋找 ${\text{cut}}_1$，當 ${\text{cut}}_1$ 確定之后 ${\text{cut}}_2$ 也可以確定。

尋找 ${\text{cut}}_1$ 可以使用二分查找實現。由于兩個數組都是升序數組，${\text{nums}}_1[{\text{cut}}_1?1]\le {\text{nums}}_1[{\text{cut}}_1]$ 和 ${\text{nums}}_2[{\text{cut}}_2?1]\le {\text{nums}}_2[{\text{cut}}_2]$ 都滿足，因此只需要滿足 ${\text{nums}}_1[{\text{cut}}_1?1]\le {\text{nums}}_2[{\text{cut}}_2]$ 和 ${\text{nums}}_2[{\text{cut}}_2?1]\le {\text{nums}}_1[{\text{cut}}_1]$ 即可。二分查找需要查找滿足 ${\text{nums}}_1[{\text{cut}}_1?1]\le {\text{nums}}_2[{\text{cut}}_2]$ 的最大下標 ${\text{cut}}_1$。

用 $\text{low}$ 和 $\text{high}$ 分別表示二分查找的下標范圍的下界和上界，初始時 $\text{low}=0$，$\text{high}=m$。每次查找時，取 ${\text{index}}_1$ 為 $\text{low}$ 和 $\text{high}$ 的平均數向上取整，并得到 ${\text{index}}_2=\text{lowerSize}?{\text{index}}_1$，比較 ${\text{nums}}_1[{\text{index}}_1?1]$ 和 ${\text{nums}}_2[{\text{index}}_2]$ 的大小關系，調整查找的下標范圍。

• 如果 ${\text{nums}}_1[{\text{index}}_1?1]\le {\text{nums}}_2[{\text{index}}_2]$，則 ${\text{cut}}_1\ge {\text{index}}_1$，因此在下標范圍 $[{\text{index}}_1,\text{high}]$ 中繼續(xù)查找。

• 如果 ${\text{nums}}_1[{\text{index}}_1?1]>{\text{nums}}_2[{\text{index}}_2]$，則 ${\text{cut}}_1<{\text{index}}_1$，因此在下標范圍 $[\text{low},{\text{index}}_1?1]$ 中繼續(xù)查找。

當 $\text{low}=\text{high}$ 時，查找結束，此時 $\text{low}$ 即為 ${\text{cut}}_1$。

得到 ${\text{cut}}_1$ 之后即可得到 ${\text{cut}}_2$，${\text{nums}}_1[{\text{cut}}_1?1]$ 和 ${\text{nums}}_2[{\text{cut}}_2?1]$ 中的最大值是前半部分的最大值，${\text{nums}}_1[{\text{cut}}_1]$ 和 ${\text{nums}}_2[{\text{cut}}_2]$ 中的最小值是后半部分的最小值。根據前半部分的最大值和后半部分的最小值即可計算中位數。

• 當 $\text{total}$ 是奇數時，中位數是前半部分的最大值。

• 當 $\text{total}$ 是偶數時，中位數是前半部分的最大值與后半部分的最小值的平均數。

該解法的時間復雜度是 $O(\log m)$，優(yōu)于解法一的 $O(\log (m+n))$。

實現方面，由于只需要在一個數組中二分查找，因此可以選擇較短的數組二分查找，時間復雜度是 $O(\log \min (m,n))$。

以下用一個例子說明上述過程。

兩個數組是 ${\text{nums}}_1=[1,2,3,4,5]$，${\text{nums}}_2=[1,2,3,4,5,6,7,8,9,10]$，兩個數組的長度分別是 $m=5$，$n=10$，長度之和是 $15$，前半部分的元素個數是 $8$。初始時，$\text{low}=0$，$\text{high}=5$。

1. 根據 $\text{low}=0$ 和 $\text{high}=5$ 計算得到 ${\text{index}}_1=3$，${\text{index}}_2=5$。由于 ${\text{nums}}_1[2]\le {\text{nums}}_2[5]$，因此將 $\text{low}$ 更新為 $3$。

2. 根據 $\text{low}=3$ 和 $\text{high}=5$ 計算得到 ${\text{index}}_1=4$，${\text{index}}_2=4$。由于 ${\text{nums}}_1[3]\le {\text{nums}}_2[4]$，因此將 $\text{low}$ 更新為 $4$。

3. 根據 $\text{low}=4$ 和 $\text{high}=5$ 計算得到 ${\text{index}}_1=5$，${\text{index}}_2=3$。由于 ${\text{nums}}_1[4]>{\text{nums}}_2[3]$，因此將 $\text{high}$ 更新為 $4$。

4. 此時 $\text{low}=\text{high}$，二分查找結束。根據 $\text{low}=4$ 計算得到 ${\text{cut}}_1=4$，${\text{cut}}_2=4$，前半部分的最大值是 $4$，后半部分的最小值是 $5$。由于兩個數組的長度之和是奇數，因此中位數是前半部分的最大值，中位數是 $4$。

代碼

class Solution {public double findMedianSortedArrays(int[] nums1, int[] nums2) {return nums1.length <= nums2.length ? findMedian(nums1, nums2) : findMedian(nums2, nums1);}public double findMedian(int[] shorter, int[] longer) {int length1 = shorter.length, length2 = longer.length;int total = length1 + length2;int lowerSize = (total + 1) / 2;int low = 0, high = length1;while (low < high) {int index1 = low + (high - low + 1) / 2;int index2 = lowerSize - index1;int left1 = shorter[index1 - 1];int right2 = longer[index2];if (left1 <= right2) {low = index1;} else {high = index1 - 1;}}int cut1 = low, cut2 = lowerSize - low;int lower1 = cut1 == 0 ? Integer.MIN_VALUE : shorter[cut1 - 1];int lower2 = cut2 == 0 ? Integer.MIN_VALUE : longer[cut2 - 1];int higher1 = cut1 == length1 ? Integer.MAX_VALUE : shorter[cut1];int higher2 = cut2 == length2 ? Integer.MAX_VALUE : longer[cut2];int lowerMax = Math.max(lower1, lower2), higherMin = Math.min(higher1, higher2);if (total % 2 == 1) {return lowerMax;} else {return (lowerMax + higherMin) / 2.0;}}
}

復雜度分析

• 時間復雜度：$O(\log \min (m,n))$，其中 $m$ 和 $n$ 分別是數組 ${\text{nums}}_1$ 和 ${\text{nums}}_2$ 的長度。在較短的數組中二分查找，范圍是 $[0,\min (m,n)]$，二分查找的次數是 $O(\log \min (m,n))$，每次查找的時間是 $O(1)$，因此時間復雜度是 $O(\log \min (m,n))$。

• 空間復雜度：$O(1)$。