問題描述：

給定兩個大小為 m 和 n 的正序(從小到大)數組 nums1 和 nums2。請你找出并返回這兩個正序數組的中位數。要求設計一個時間復雜度為 O(log (m+n)) 的算法解決此問題。

示例 1：

輸入：nums1 = [1,3], nums2 = [2]

輸出：2.00000

解釋：合并數組 = [1,2,3] ，中位數 2

示例 2：

輸入：nums1 = [1,2], nums2 = [3,4]

輸出：2.50000

解釋：合并數組 = [1,2,3,4] ，中位數 (2 + 3) / 2 = 2.5

示例 3：

輸入：nums1 = [0,0], nums2 = [0,0]

輸出：0.00000

示例 4：

輸入：nums1 = [], nums2 = [1]

輸出：1.00000

示例 5：

輸入：nums1 = [2], nums2 = []

輸出：2.00000

提示：

nums1.length == m

nums2.length == n

0 <= m <= 1000

0 <= n <= 1000

1 <= m + n <= 2000

-106 <= nums1[i], nums2[i] <= 106

解題思路：

根據中位數的定義，當 m+n 是奇數時，中位數是兩個有序數組中的第 (m+n)/2個元素，當 m+n 是偶數時，中位數是兩個有序數組中的第 (m+n)/2個元素和第 (m+n)/2+1 個元素的平均值。因此，這道題可以轉化成尋找兩個有序數組中的第 k 小的數，其中 k 為 (m+n)/2 或 (m+n)/2+1。假設兩個有序數組分別是A 和B。要找到第 k 個元素，我們可以比較A[k/2?1] 和 B[k/2?1]，其中 /?表示整數除法。由于 A[k/2?1] 和 B[k/2?1] 的前面分別有 A[0..k/2?2] 和 B[0..k/2?2]，即 k/2?1 個元素，對于 A[k/2?1] 和 B[k/2?1] 中的較小值，最多只會有(k/2?1)+(k/2?1)≤k?2 個元素比它小，那么它就不能是第 kk 小的數了。

因此我們可以歸納出三種情況：

• 如果 A[k/2?1]

• 如果 A[k/2?1]>B[k/2?1]，則可以排除 B[0] 到 B[k/2?1]。

• 如果 A[k/2?1]=B[k/2?1]，則可以歸入第一種情況處理。

可以看到，比較 A[k/2?1] 和 B[k/2?1] 之后，可以排除 k/2 個不可能是第 k 小的數，查找范圍縮小了一半。同時，我們將在排除后的新數組上繼續進行二分查找，并且根據我們排除數的個數，減少 k 的值，這是因為我們排除的數都不大于第 k 小的數。

有以下三種情況需要特殊處理：

• 如果 A[k/2?1] 或者 B[k/2?1] 越界，那么我們可以選取對應數組中的最后一個元素。在這種情況下，我們必須根據排除數的個數減少 k 的值，而不能直接將 k 減去 k/2。

• 如果一個數組為空，說明該數組中的所有元素都被排除，我們可以直接返回另一個數組中第 k 小的元素。

• 如果 k=1，我們只要返回兩個數組首元素的最小值即可。

用一個例子說明上述算法。假設兩個有序數組如下：

A:1349B:123456789

兩個有序數組的長度分別是 4 和 9，長度之和是 13，中位數是兩個有序數組中的第 7 個元素，因此需要找到第 k=7 個元素。

比較兩個有序數組中下標為 k/2?1=2 的數，即 A[2] 和 B[2]，如下面所示：

A: 1 3 4 9 ? ?↑

B: 1 2 3 4 5 6 7 8 9 ? ?↑

由于 A[2]>B[2]，因此排除 B[0] 到 B[2]，即數組B 的下標偏移(offset)變為 3，同時更新 k 的值：k=k?k/2=4。

下一步尋找，比較兩個有序數組中下標為 k/2?1=1 的數，即 A[1] 和 B[4]，如下面所示，其中方括號部分表示已經被排除的數。

A: 1 3 4 9 ? ↑

B: [1 2 3] 4 5 6 7 8 9 ? ? ? ?↑

由于 A[1]

下一步尋找，比較兩個有序數組中下標為 k/2?1=0 的數，即比較 A[2] 和 B[3]，如下面所示，其中方括號部分表示已經被排除的數。

A: [1 3] 4 9 ? ? ?↑

B: [1 2 3] 4 5 6 7 8 9 ? ? ? ↑

由于 A[2]=B[3]，根據之前的規則，排除 A 中的元素，因此排除 A[2]，即數組 A 的下標偏移變為 3，同時更新 k 的值：k=k?k/2=1。

由于 k 的值變成 1，因此比較兩個有序數組中的未排除下標范圍內的第一個數，其中較小的數即為第 k 個數，由于 A[3]>B[3]，因此第 k 個數是 B[3]=4。

A: [1 3 4] 9 ? ? ? ↑

B: [1 2 3] 4 5 6 7 8 9 ? ? ? ↑

算法代碼：

class?Solution?{

????public?double?findMedianSortedArrays(int[]?nums1,?int[]?nums2)?{

????????int?length1?=?nums1.length,?length2?=?nums2.length;

????????int?totalLength?=?length1?+?length2;

????????if(totalLength?%?2?==?1){

????????????int?midIndex?=?totalLength?/?2;

????????????double?median?=?getKthElement(nums1,nums2,midIndex+1);

????????????return?median;

????????}else{

????????????int?midIndex1?=?totalLength?/?2?-?1,?midIndex2?=?totalLength?/?2;

????????????double?median?=?(getKthElement(nums1,?nums2,?midIndex1?+?1)?+?getKthElement(nums1,?nums2,?midIndex2?+1))?/?2.0;

????????????return?median;

????????}

????}

????public?int?getKthElement(int[]?nums1,?int[]?nums2,?int?k)?{

????????/*?主要思路：要找到第 k (k>1)?小的元素，那么就取 pivot1 = nums1[k/2-1]?和 pivot2 = nums2[k/2-1]?進行比較

?????????*?這里的?"/"?表示整除

?????????*?nums1?中小于等于?pivot1?的元素有?nums1[0?..?k/2-2]?共計?k/2-1?個

?????????*?nums2?中小于等于?pivot2?的元素有?nums2[0?..?k/2-2]?共計?k/2-1?個

?????????*?取?pivot?=?min(pivot1,?pivot2)，兩個數組中小于等于?pivot?的元素共計不會超過?(k/2-1)?+?(k/2-1)?<=?k-2?個

?????????*?這樣?pivot?本身最大也只能是第?k-1?小的元素

?????????*?如果 pivot = pivot1，那么 nums1[0 .. k/2-1]?都不可能是第 k 小的元素。把這些元素全部?"刪除"，剩下的作為新的 nums1 數組

?????????*?如果 pivot = pivot2，那么 nums2[0 .. k/2-1]?都不可能是第 k 小的元素。把這些元素全部?"刪除"，剩下的作為新的 nums2 數組

?????????*?由于我們?"刪除"?了一些元素(這些元素都比第?k?小的元素要小)，因此需要修改?k?的值，減去刪除的數的個數

?????????*/

????????int?length1?=?nums1.length,?length2?=?nums2.length;

????????int?index1?=?0,?index2?=?0;

????????int?kthElement?=?0;

????????while?(true)?{

????????????//?邊界情況

????????????if?(index1?==?length1)?{

????????????????return?nums2[index2?+?k?-?1];

????????????}

????????????if?(index2?==?length2)?{

????????????????return?nums1[index1?+?k?-?1];

????????????}

????????????if?(k?==?1)?{

????????????????return?Math.min(nums1[index1],?nums2[index2]);

????????????}

????????????//?正常情況

????????????int?half?=?k?/?2;

????????????int?newIndex1?=?Math.min(index1?+?half,?length1)?-?1;

????????????int?newIndex2?=?Math.min(index2?+?half,?length2)?-?1;

????????????int?pivot1?=?nums1[newIndex1],?pivot2?=?nums2[newIndex2];

????????????if?(pivot1?<=?pivot2)?{

????????????????k?-=?(newIndex1?-?index1?+?1);

????????????????index1?=?newIndex1?+?1;

????????????}?else?{

????????????????k?-=?(newIndex2?-?index2?+?1);

????????????????index2?=?newIndex2?+?1;

????????????}

????????}

????}

}

總結

以上是生活随笔為你收集整理的未能比较数组中的两个元素_算法3 寻找两个正序数组的中序数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。