4. Median of Two Sorted Arrays
題目敘述
Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.
The overall run time complexity should be O(log (m+n)).
Example 1:
Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.
Example 2:
Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.
Constraints:
nums1.length == mnums2.length == n0 <= m <= 10000 <= n <= 10001 <= m + n <= 2000-10**6 <= nums1[i], nums2[i] <= 10**6
題目翻譯
有兩個排序過的陣列 nums1 和 nums2，其長度分別是 m 和 n。回傳這這兩個陣列的中間值，並且其時間複雜度需要在 O(log(m+n))。
解法解析
這個題目找出中間值並不難，難的在於其時間複雜度要在 O(log(m+n))。在 Discuss 中投票數最多的一篇討論(參考1)有講解怎麼達到 O(log(m+n))，但還是有點不太懂。後來在 YouTube 找到這一則影片講解才終於比較理解。
我這邊大概簡述期概念，就是因為是要找出中間值，所以可以預想有幾種情境。中間數會有左右兩邊的數個字為 L 和 R。而這兩個數，有可能在同一個 Array 或是不同的 Array。其規則大概是 L = (N-1)/2 和 R = N/2，N 是陣列的總長度。將較短的陣列設定為 n1，較長的為 n2。先將 L 設定為 n1 的最後一位，將 R 設為 n2 的第一位。遍歷 n1 去比較 L 和 R 的大小，然後慢慢的擴展 L 和 R 的位置。
解法範例
Go
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
if len(nums1) < len(nums2) {
nums1, nums2 = nums2, nums1
}
total := len(nums1) + len(nums2)
half := total / 2
m := len(nums1)
n := len(nums2)
l := 0
r := n - 1
for true {
left1 := math.MinInt64
left2 := math.MinInt64
right1 := math.MaxInt64
right2 := math.MaxInt64
i := 0
j := 0
if l <= r {
j = (l + r) / 2
i = half - j - 2
} else {
j = -1
i = half - 1
}
if i >= 0 {
left1 = nums1[i]
}
if j >= 0 {
left2 = nums2[j]
}
if i+1 < m {
right1 = nums1[i+1]
}
if j+1 < n {
right2 = nums2[j+1]
}
if left1 <= right2 && left2 <= right1 {
if total%2 == 1 {
return min(right1, right2)
} else {
return (min(right1, right2) + max(left1, left2)) / float64(2)
}
} else if left2 > right1 {
r = j - 1
} else {
l = j + 1
}
}
return 0
}
func max(a, b int) float64 {
if a > b {
return float64(a)
}
return float64(b)
}
func min(a, b int) float64 {
if a < b {
return float64(a)
}
return float64(b)
}
JavaScript
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number}
*/
var findMedianSortedArrays = function (nums1, nums2) {
const [shortList, longList] = nums1.length < nums2.length ? [nums1, nums2] : [nums2, nums1];
const totalLength = shortList.length + longList.length;
let shortStartIdx = 0, shortEndIdx = shortList.length - 1;
while (shortStartIdx <= shortEndIdx) {
const shortMidIdx = Math.floor((shortStartIdx + shortEndIdx) / 2);
const longMidIdx = Math.floor(totalLength / 2) - shortMidIdx - 2;
const shortLeft = shortMidIdx === 0 ? Number.NEGATIVE_INFINITY : shortList[shortMidIdx - 1];
if (shortMid < longMid) {
shortStartIdx = shortMidIdx + 1;
} else if (shortMid > longMid) {
shortEndIdx = shortMidIdx - 1;
} else {
return shortMid;
}
}
};
Kotlin
import kotlin.math.max
import kotlin.math.min
class Solution {
fun findMedianSortedArrays(nums1: IntArray, nums2: IntArray): Double {
if (nums1.isEmpty()) return findMedianSortedArray(nums2)
if (nums2.isEmpty()) return findMedianSortedArray(nums1)
return if (nums1.size <= nums2.size) findMedianSortedArraysNonEmpty(nums1, nums2)
else findMedianSortedArraysNonEmpty(nums2, nums1)
}
/**
* Finds median of two non-empty sorted arrays. Size of [nums1] must be less or equal to size of
* [nums2]
*/
private fun findMedianSortedArraysNonEmpty(nums1: IntArray, nums2: IntArray): Double {
val size = nums1.size + nums2.size
val half = size / 2
var left = 0
var right = nums1.size
while (left <= right) {
val m1 = left + (right - left) / 2
val m2 = half - m1
val n1Left = if (m1 > 0) nums1[m1 - 1] else Int.MIN_VALUE
val n1Right = if (m1 < nums1.size) nums1[m1] else Int.MAX_VALUE
val n2Left = if (m2 > 0) nums2[m2 - 1] else Int.MIN_VALUE
val n2Right = if (m2 < nums2.size) nums2[m2] else Int.MAX_VALUE
if (n1Left <= n2Right && n2Left <= n1Right)
return if (size % 2 == 1) min(n1Right, n2Right).toDouble()
else (max(n1Left, n2Left) + min(n1Right, n2Right)) / 2.0
else if (n1Left > n2Right) right = m1 - 1 else left = m1 + 1
}
return 0.0 // should not be reachable
}
private fun findMedianSortedArray(nums: IntArray): Double {
val mid = nums.size / 2
return if (nums.size % 2 == 1) nums[mid].toDouble() else (nums[mid - 1] + nums[mid]) / 2.0
}
}
PHP
class Solution
{
/**
* @param Integer[] $nums1
* @param Integer[] $nums2
* @return Float
*/
function findMedianSortedArrays($nums1, $nums2)
{
$newArray = array_merge($nums1, $nums2);
sort($newArray);
$start = 0;
$end = count($newArray) - 1;
$middle = floor(($start + $end) / 2);
if (count($newArray) % 2 == 0) {
$median = ($newArray[$middle] + $newArray[$middle + 1]) / 2;
} else {
$median = $newArray[$middle];
}
return $median;
}
}
Python
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
short_list, long_list = nums1, nums2
if len(nums1) > len(nums2):
short_list, long_list = nums2, nums1
total_len = len(nums1) + len(nums2)
short_start_idx, short_end_idx = 0, len(short_list) - 1
while True:
short_val_idx = (short_start_idx + short_end_idx) // 2
long_val_idx = (total_len) // 2 - short_val_idx - 2
short_left = short_list[short_val_idx] if short_val_idx >= 0 else float(
'-inf')
long_left = long_list[long_val_idx] if long_val_idx >= 0 else float(
'-inf')
short_right = short_list[short_val_idx +
1] if short_val_idx + 1 < len(short_list) else float('inf')
long_right = long_list[long_val_idx +
1] if long_val_idx + 1 < len(long_list) else float('inf')
if short_left > long_right:
short_end_idx = short_val_idx - 1
elif long_left > short_right:
short_start_idx = short_val_idx + 1
else:
if total_len % 2:
return min(short_right, long_right)
else:
return (max(short_left, long_left) + min(short_right, long_right)) / 2
Rust
impl Solution {
pub fn find_median_sorted_arrays(nums1: Vec<i32>, nums2: Vec<i32>) -> f64 {
let mut offset1 = 0;
let mut offset2 = 0;
let mut num1 = 0;
let mut num2 = 0;
let mut result:f64;
let length = nums1.len() + nums2.len();
loop {
if (offset1 + offset2) * 2 > length {
break;
}
num1 = num2;
let mut move_which = 1;
if offset1 >= nums1.len() {
move_which = 2;
} else if offset2 >=nums2.len() {
move_which = 1;
} else if nums1[offset1] > nums2[offset2] {
move_which = 2;
}
if move_which == 1 {
num2 = nums1[offset1];
offset1 = offset1 + 1;
} else {
num2 = nums2[offset2];
offset2 = offset2 + 1;
}
}
if length % 2 == 0 {
result = (num1 as f64 + num2 as f64) / 2.0;
} else {
result = num2 as f64;
}
return result;
}
}
Swift
class Solution {
func findMedianSortedArrays(_ nums1: [Int], _ nums2: [Int]) -> Double {
guard nums1.count <= nums2.count else {
return findMedianSortedArrays(nums2, nums1)
}
let oneSize = nums1.count
let twoSize = nums2.count
let total = oneSize + twoSize
var start = 0
var end = oneSize
while start <= end {
let midX = (start + end) / 2
let midY = (total + 1) / 2 - midX
let xLeft = midX == 0 ? Int.min : nums1[midX - 1]
let xRight = midX == oneSize ? Int.max : nums1[midX]
let yLeft = midY == 0 ? Int.min : nums2[midY - 1]
let yRight = midY == twoSize ? Int.max : nums2[midY]
if xLeft <= yRight && yLeft <= xRight {
if total % 2 == 0 {
return Double((max(xLeft, yLeft) + min(xRight, yRight))) / 2.0
} else {
return Double(max(xLeft, yLeft))
}
} else if yLeft > xRight {
start = midX + 1
} else {
end = midX - 1
}
}
return -1
}
}