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 == m
• nums2.length == n
• 0 <= m <= 1000
• 0 <= n <= 1000
• 1 <= 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
    }
}

Reference

• https://leetcode.com/problems/median-of-two-sorted-arrays/discuss/2471/Very-concise-O(log(min(MN)))-iterative-solution-with-detailed-explanation