LeetCode 004 Median of Two Sorted Arrays 詳細分析

摘要： 題目連結： https://leetcode.com/problems/median-of-two-sorted-arrays/ 我一直會卡在這道題上，在網上看了半個小時的部落格，愣是沒看懂。後來看到 YouTube 上有一個印度大哥的講解，豁然開朗。 印度大哥的視訊地址： Bi...

題目連結： ofollow,noindex">https://leetcode.com/problems/median-of-two-sorted-arrays/

我一直會卡在這道題上，在網上看了半個小時的部落格，愣是沒看懂。後來看到 YouTube 上有一個印度大哥的講解，豁然開朗。

印度大哥的視訊地址： Binary Search : Median of two sorted arrays of different sizes.

題目描述

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)).

You may assume nums1 and nums2 cannot be both empty.

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

題目分析

其實這道題我卡就卡在，一直沒有想清楚應該如何劃分兩個陣列。直接看LeetCode論壇上的答案，也一直沒有搞懂。本題只是想求中位數，並不用管其他的數字。

那麼核心就在於，如何劃分兩個陣列，使得兩個陣列組合起來後，成為一個在中位數附近相對有序的陣列即可。

具體例項分析

演算法分析

定義兩個變數 partitionX、 partitionY，分別分割X陣列和Y陣列，記為X1, X2, Y1, Y2。使得

len(X1) + len(Y1) == len(X2) + len(Y2)
或
len(X1) + len(Y1) == len(X2) + len(Y2) + 1

並且使得 max(X1) < min(Y2), max(Y1) < min(X2)，這樣陣列就被完整地分成了兩部分。

如果兩個陣列長度的和是奇數，那麼必然是 max(X1, Y1)了；

如果兩個陣列長度的和是偶數，那麼是 (max(X1, Y1) + min(X2, Y2)) / 2。

程式碼實現

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
if (nums1.length > nums2.length) {
return findMedianSortedArrays(nums2, nums1);
}

int x = nums1.length, y = nums2.length;
int low = 0, high = x;

while (low <= high) {
int partitionX = (low + high) / 2;
int partitionY = (x + y + 1) / 2 - partitionX;

int maxLeftX = (partitionX == 0) ? Integer.MIN_VALUE : nums1[partitionX - 1];
int maxLeftY = (partitionY == 0) ? Integer.MIN_VALUE : nums2[partitionY - 1];

int minRightX = (partitionX == x) ? Integer.MAX_VALUE : nums1[partitionX];
int minRightY = (partitionY == y) ? Integer.MAX_VALUE : nums2[partitionY];

if (maxLeftX <= minRightY && maxLeftY <= minRightX) {
if ((x + y) % 2 == 0) {
return (Math.max(maxLeftX, maxLeftY) + Math.min(minRightX, minRightY)) / 2.0;
} else {
return Math.max(maxLeftX, maxLeftY);
}
} else if (minRightX < maxLeftY) {
low = partitionX + 1;
} else {
high = partitionX - 1;
}
}

throw new RuntimeException();
}

總結

這道題如果能把圖畫出來，理解起來就很容易。但是這道題在LeetCode中的難度是 hard ，因為編寫程式碼並不容易，有很多邊界條件：

1. 陣列長度的奇偶
2. 移動過程中，某個陣列被切割後可能為空