4. Median of Two Sorted Arrays

Leetcode 問題: 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)).

傳入 2 個已排序數字陣列,回傳兩個排序陣列的中位數,複雜度必須為 O(log (m+n)).

演算法原理

Binary Search : Median of two sorted arrays of different sizes

答案

Golang

func findMedianSortedArrays(nums_list_1 []int, nums_list_2 []int) float64 {
    // 假设 nums1 的长度小
    if len(nums_list_1) > len(nums_list_2) {
        // 若數字清單 1 長度大於數字清單 2,將清單較短的數字清單 2 優先傳入第一個參數
        return findMedianSortedArrays(nums_list_2, nums_list_1)
    }
    // 「數字清單 1」左方數字索引
    num1_left_num_index := 0
    // 「數字清單 1」右方數字索引
    num1_right_nums_index := len(nums_list_1)
    // 所有數字中位數可能位置,全部長度+1,bit 往右位移除 2
    all_nums_list_divide_position := (len(nums_list_1) + len(nums_list_2) + 1) >> 1

    // 「數字清單 1」中位數位置
    nums1_median_index := 0
    // 「數字清單 2」中位數位置
    nums2_median_index := 0

    // === 中位數區塊劃分 ===
    for num1_left_num_index <= num1_right_nums_index {
        // 「當左方數字索引」比「右方數字索引」還要小,表示搜尋的數字還沒交叉重複到

        // 數字清單 1 中位數位置 = 目前左方最小數字位置 + 右方剩餘數字取中位數 bit 往右位移(除 2)
        // 中位數分界點,左側是 median_index -1,右側是 median_index,
        // nums1:  ……………… nums1[nums1_median_index-1] | nums1[nums1_median_index] ……………………
        // nums2:  ……………… nums2[nums2_median_index-1] | nums2[nums2_median_index] ……………………
        nums1_median_index = num1_left_num_index + (num1_right_nums_index-num1_left_num_index)>>1
        // 數字清單 2 中位數位置 =  所有數字中位數可能位置 - 數字清單 1 中位數位置
        nums2_median_index = all_nums_list_divide_position - nums1_median_index

        if nums1_median_index > 0 && nums_list_1[nums1_median_index-1] > nums_list_2[nums2_median_index] { // nums1 中的分界线划多了,要向左边移动
            // 「數字清單 1」中位數位置不是第一個數字
            // 「數字清單 1」中位數左側數字比「數字清單 2」右側中位數還大(排序過的數字左側應比右側小)
            // 表示整個數字列表的中位數在「數字清單 1」目前中位數之前
            // 「數字清單 1」右方數字索引往左側移動,找「數字清單 1」中位數前面小一點的數字
            num1_right_nums_index = nums1_median_index - 1
        } else if nums1_median_index != len(nums_list_1) && nums_list_1[nums1_median_index] < nums_list_2[nums2_median_index-1] { // nums1 中的分界线划少了,要向右边移动
            // 「數字清單 1」中位數位置不是最後一個數字
            // 「數字清單 1」中位數右側數字比「數字清單 2」左側中位數還小(排序過的數字右側應比左側大)
            // 「數字清單 1」中位數位置數字 比 「數字清單 2」中位數位位置的前一個數字還小
            // 「數字清單 1」左方數字索引往右側移動,找「數字清單 1」中位數後面大一點的數字
            num1_left_num_index = nums1_median_index + 1
        } else {
            // 無法再劃分左右側中位數位置
            break
        }
    }

    // === 找出中位數 ===
    // 中位數
    var median_num float64 = 0.0
    // 左側中位數
    median_num_left := 0
    // 右側中位數
    median_num_right := 0

    if nums1_median_index == 0 {
        // 「數字清單 1」中位數位置為第一個數字
        // 中位數左側數字 = 「數字清單 2」 左側第一個數字」
        median_num_left = nums_list_2[nums2_median_index-1]
    } else if nums2_median_index == 0 {
        // 「數字清單 2」中位數位置為第一個數字
        // 中位數左側數字 = 「數字清單 1」 左側第一個數字」
        median_num_left = nums_list_1[nums1_median_index-1]
    } else {
        // 中位數左側數字 = 「數字清單 1 左側位置第一個數字」與「數字清單 2 左側位置第一個數字」取最大的數字
        // 左側的數字比右側小,所以要找比較大的數字才會接近右側數字
        median_num_left = max(nums_list_1[nums1_median_index-1], nums_list_2[nums2_median_index-1])
    }

    // 判斷數字數量是奇數還是偶數
    if (len(nums_list_1)+len(nums_list_2))&1 == 1 {
        // 若數字總數量為奇數,直接回傳中位數數字
        median_num = float64(median_num_left)
        return median_num
    }

    if nums1_median_index == len(nums_list_1) {
        // 「數字清單 1」中位數位置在不在清單中,索引超出清單長度(索引從 0 開始算)
        // 中位數右側數字 = 「數字清單 2」中位數右側第一個數字
        median_num_right = nums_list_2[nums2_median_index]
    } else if nums2_median_index == len(nums_list_2) {
        // 「數字清單 2」中位數位置在不在清單中,索引超出清單長度(索引從 0 開始算)
        // 中位數右側數字 = 「數字清單 1」中位數右側第一個數字
        median_num_right = nums_list_1[nums1_median_index]
        fmt.Println("<median_num_right (2)>: num1_medium =>  nums_list_1[nums1_median_index]")
    } else {
        // 中位數右側數字 = 「數字清單 1 右側第一個數字」與「數字清單 2 右側第一個數字」取最小的數字
        // 右側的數字比左側大,所以要找比較小的數字才會接近左側數字
        median_num_right = min(nums_list_1[nums1_median_index], nums_list_2[nums2_median_index])
    }


    median_num = float64(median_num_left+median_num_right) / 2

    return median_num
}

func max(a int, b int) int {
    if a > b {
        return a
    }
    return b
}

func min(a int, b int) int {
    if a > b {
        return b
    }
    return a
}

完整程式碼

package main

import (
    "fmt"
)

type QuestionList struct {
    Parameter
    Answer
}

// para 是参数
// one 代表第一个参数
type Parameter struct {
    nums1 []int
    nums2 []int
}

// ans 是答案
// one 代表第一个答案
type Answer struct {
    one float64
}

func main() {

    question_list := []QuestionList{
        {
            Parameter{[]int{400}, []int{111, 222, 333, 444, 555, 666, 777}},
            Answer{422},
        },
        {
            Parameter{[]int{700}, []int{111, 222, 333, 444, 555, 666, 777}},
            Answer{499.5},
        },
        {
            Parameter{[]int{600}, []int{111, 222, 333, 444, 555, 666, 777}},
            Answer{499.5},
        },
        {
            Parameter{[]int{500}, []int{111, 222, 333, 444, 555, 666, 777}},
            Answer{472},
        },
        {
            Parameter{[]int{1, 3, 5, 7, 9}, []int{2, 3, 4, 7, 11, 13}},
            Answer{3.5},
        },
        {
            Parameter{[]int{1, 3}, []int{2}},
            Answer{2.0},
        },

        {
            Parameter{[]int{1, 2}, []int{3, 4}},
            Answer{2.5},
        },
    }

    fmt.Printf("------------------------Leetcode Problem 4------------------------\n")

    for _, question := range question_list {
        // 問題參數
        Ans, Param := question.Answer, question.Parameter
        fmt.Printf("【input】:%+v    answer:%+v    【output】:%+v\n", Param, Ans, findMedianSortedArrays(Param.nums1, Param.nums2))
    }
    fmt.Printf("\n\n\n")
}

func findMedianSortedArrays(nums_list_1 []int, nums_list_2 []int) float64 {
    // 假设 nums1 的长度小
    if len(nums_list_1) > len(nums_list_2) {
        // 若數字清單 1 長度大於數字清單 2,將清單較短的數字清單 2 優先傳入第一個參數
        return findMedianSortedArrays(nums_list_2, nums_list_1)
    }
    // 「數字清單 1」左方數字索引
    num1_left_num_index := 0
    // 「數字清單 1」右方數字索引
    num1_right_nums_index := len(nums_list_1)
    // 所有數字中位數可能位置,全部長度+1,bit 往右位移除 2
    all_nums_list_divide_position := (len(nums_list_1) + len(nums_list_2) + 1) >> 1

    // 「數字清單 1」中位數位置
    nums1_median_index := 0
    // 「數字清單 2」中位數位置
    nums2_median_index := 0

    // === 中位數區塊劃分 ===
    for num1_left_num_index <= num1_right_nums_index {
        // 「當左方數字索引」比「右方數字索引」還要小,表示搜尋的數字還沒交叉重複到

        // 數字清單 1 中位數位置 = 目前左方最小數字位置 + 右方剩餘數字取中位數 bit 往右位移(除 2)
        // 中位數分界點,左側是 median_index -1,右側是 median_index,
        // nums1:  ……………… nums1[nums1_median_index-1] | nums1[nums1_median_index] ……………………
        // nums2:  ……………… nums2[nums2_median_index-1] | nums2[nums2_median_index] ……………………
        nums1_median_index = num1_left_num_index + (num1_right_nums_index-num1_left_num_index)>>1
        // 數字清單 2 中位數位置 =  所有數字中位數可能位置 - 數字清單 1 中位數位置
        nums2_median_index = all_nums_list_divide_position - nums1_median_index

        if nums1_median_index > 0 && nums_list_1[nums1_median_index-1] > nums_list_2[nums2_median_index] { // nums1 中的分界线划多了,要向左边移动
            // 「數字清單 1」中位數位置不是第一個數字
            // 「數字清單 1」中位數左側數字比「數字清單 2」右側中位數還大(排序過的數字左側應比右側小)
            // 表示整個數字列表的中位數在「數字清單 1」目前中位數之前
            // 「數字清單 1」右方數字索引往左側移動,找「數字清單 1」中位數前面小一點的數字
            num1_right_nums_index = nums1_median_index - 1
        } else if nums1_median_index != len(nums_list_1) && nums_list_1[nums1_median_index] < nums_list_2[nums2_median_index-1] { // nums1 中的分界线划少了,要向右边移动
            // 「數字清單 1」中位數位置不是最後一個數字
            // 「數字清單 1」中位數右側數字比「數字清單 2」左側中位數還小(排序過的數字右側應比左側大)
            // 「數字清單 1」中位數位置數字 比 「數字清單 2」中位數位位置的前一個數字還小
            // 「數字清單 1」左方數字索引往右側移動,找「數字清單 1」中位數後面大一點的數字
            num1_left_num_index = nums1_median_index + 1
        } else {
            // 無法再劃分左右側中位數位置
            break
        }
    }

    // === 找出中位數 ===
    // 中位數
    var median_num float64 = 0.0
    // 左側中位數
    median_num_left := 0
    // 右側中位數
    median_num_right := 0

    if nums1_median_index == 0 {
        // 「數字清單 1」中位數位置為第一個數字
        // 中位數左側數字 = 「數字清單 2」 左側第一個數字」
        median_num_left = nums_list_2[nums2_median_index-1]
    } else if nums2_median_index == 0 {
        // 「數字清單 2」中位數位置為第一個數字
        // 中位數左側數字 = 「數字清單 1」 左側第一個數字」
        median_num_left = nums_list_1[nums1_median_index-1]
    } else {
        // 中位數左側數字 = 「數字清單 1 左側位置第一個數字」與「數字清單 2 左側位置第一個數字」取最大的數字
        // 左側的數字比右側小,所以要找比較大的數字才會接近右側數字
        median_num_left = max(nums_list_1[nums1_median_index-1], nums_list_2[nums2_median_index-1])
    }

    // 判斷數字數量是奇數還是偶數
    if (len(nums_list_1)+len(nums_list_2))&1 == 1 {
        // 若數字總數量為奇數,直接回傳中位數數字
        median_num = float64(median_num_left)
        return median_num
    }

    if nums1_median_index == len(nums_list_1) {
        // 「數字清單 1」中位數位置在不在清單中,索引超出清單長度(索引從 0 開始算)
        // 中位數右側數字 = 「數字清單 2」中位數右側第一個數字
        median_num_right = nums_list_2[nums2_median_index]
    } else if nums2_median_index == len(nums_list_2) {
        // 「數字清單 2」中位數位置在不在清單中,索引超出清單長度(索引從 0 開始算)
        // 中位數右側數字 = 「數字清單 1」中位數右側第一個數字
        median_num_right = nums_list_1[nums1_median_index]
        fmt.Println("<median_num_right (2)>: num1_medium =>  nums_list_1[nums1_median_index]")
    } else {
        // 中位數右側數字 = 「數字清單 1 右側第一個數字」與「數字清單 2 右側第一個數字」取最小的數字
        // 右側的數字比左側大,所以要找比較小的數字才會接近左側數字
        median_num_right = min(nums_list_1[nums1_median_index], nums_list_2[nums2_median_index])
    }


    median_num = float64(median_num_left+median_num_right) / 2

    return median_num
}

func max(a int, b int) int {
    if a > b {
        return a
    }
    return b
}

func min(a int, b int) int {
    if a > b {
        return b
    }
    return a
}

Python

import sys
from typing import List


class Solution(object):
    def findMedianSortedArrays(self, nums_list_1: List[int], nums_list_2: List[int]) -> float:
        # https://github.com/mission-peace/interview/blob/master/src/com/interview/binarysearch/MedianOfTwoSortedArrayOfDifferentLength.java
        # https://discuss.leetcode.com/topic/4996/share-my-o-log-min-m-n-solution-with-explanation
        # https://discuss.leetcode.com/topic/16797/very-concise-o-log-min-m-n-iterative-solution-with-detailed-explanation
        # https://books.halfrost.com/leetcode/ChapterFour/0001~0099/0004.Median-of-Two-Sorted-Arrays/
        # 「數字清單 1」數量
        nums_list_1_length = len(nums_list_1)
        # 「數字清單 2」數量
        nums_list_2_length = len(nums_list_2)

        if nums_list_1_length > nums_list_2_length:
            # 若「數字清單 1」數量大於「數字清單 2」,將交換數字清單順序,將小的優先傳入
            return self.findMedianSortedArrays(nums_list_2, nums_list_1)

        # 「數字清單 1」左側檢查位置(從第一個開始往右檢查)
        nums_list_1_left_index = 0
        # 「數字清單 1」右側檢查位置(從最後一個開始往左檢查)
        nums_list_1_right_index = nums_list_1_length
        # 所有數字中位數可能位置,全部長度+1,bit 往右位移除 2
        all_nums_list_divide_position = (nums_list_1_length + nums_list_2_length + 1) >> 1
        # 「數字清單 1」中位數位置
        nums_list_1_median_partition_index = 0
        # 「數字清單 2」中位數位置
        nums_list_2_median_partition_index = 0

        # 找尋中位數位置
        while nums_list_1_left_index <= nums_list_1_right_index:
            # 「數字清單 1」左側檢查位置小於右側位置,繼續檢查
            # 「數字清單 1」中位數檢查拆分位置 = 目前左方最小數字位置 + 右方剩餘數字取中位數 bit 往右位移除 2
            nums_list_1_median_partition_index: int = nums_list_1_left_index + (
                    (nums_list_1_right_index - nums_list_1_left_index) >> 1)
            # 「數字清單 2」中位數檢查拆分位置 = 所有數字中位數可能位置 - 數字清單 1 中位數位置
            nums_list_2_median_partition_index: int = all_nums_list_divide_position - nums_list_1_median_partition_index

            if nums_list_1_median_partition_index > 0 and nums_list_1[nums_list_1_median_partition_index - 1] > \
                    nums_list_2[nums_list_2_median_partition_index]:
                # 「數字清單 1」中位數位置不是第一個數字,且有資料
                # 「數字清單 1」中位數左側數字比「數字清單 2」右側中位數還大(排序過的數字左側應比右側小)
                # 表示整個數字列表的中位數在「數字清單 1」目前中位數之前
                # 「數字清單 1」右方數字索引往左側移動,找「數字清單 1」中位數前面小一點的數字
                nums_list_1_right_index = nums_list_1_median_partition_index - 1
            elif nums_list_1_median_partition_index != nums_list_1_length and nums_list_1[
                nums_list_1_median_partition_index] < nums_list_2[nums_list_2_median_partition_index - 1]:
                # 「數字清單 1」中位數位置不是最後一個數字,且有資料
                # 「數字清單 1」中位數右側數字比「數字清單 2」左側中位數還小(排序過的數字右側應比左側大)
                # 「數字清單 1」中位數位置數字 比 「數字清單 2」中位數位位置的前一個數字還小
                # 「數字清單 1」左方數字索引往右側移動,找「數字清單 1」中位數後面大一點的數字
                nums_list_1_left_index = nums_list_1_median_partition_index + 1
            else:
                # 無法再劃分左右側中位數位置
                break

        # === 找出中位數 ===
        # 中位數
        median_num: float = 0.0
        # 左側中位數
        median_num_left: int = 0
        # 右側中位數
        median_num_right: int = 0

        if nums_list_1_median_partition_index == 0:
            # 「數字清單 1」中位數位置為移動到第一個數字,或是沒有數字 => 「數字清單 1」左側都沒有資料
            # 中位數左側數字 = 「數字清單 2」 左側第一個數字」
            median_num_left = nums_list_2[nums_list_2_median_partition_index - 1]
        elif nums_list_2_median_partition_index == 0:
            # 「數字清單 2」中位數位置移動到第一個數字,表示數字只有一個,或是沒有數字 => 「數字清單 2」左側都沒有資料
            # 中位數左側數字 = 「數字清單 1」 左側第一個數字」
            median_num_left = nums_list_1[nums_list_1_median_partition_index - 1]
        else:
            # 「數字清單 1」與「數字清單 2」有超過一個數字,有自己的中位數,取兩個左側中位數最大的那一個
            # 左側的數字比右側小,所以要找比較大的數字才會接近右側數字
            median_num_left = max(nums_list_1[nums_list_1_median_partition_index - 1],
                                  nums_list_2[nums_list_2_median_partition_index - 1])


        if (nums_list_1_length + nums_list_2_length) & 1 == 1:
            # 若數字總數量為奇數,直接回傳中位數數字
            median_num = float(median_num_left)
            return median_num

        # 若數字總數量為偶數,取得中位數右側最小數值
        if nums_list_1_median_partition_index == nums_list_1_length:
            # 「數字清單 1」沒有數字,或者索引超出範圍 => 「數字清單 1」右側都沒有資料,使用「數字清單 2」右側資料
            median_num_right = nums_list_2[nums_list_2_median_partition_index]
        elif nums_list_2_median_partition_index == nums_list_2_length:
            # 「數字清單 2」沒有數字,或者索引超出範圍 => 「數字清單 2」右側都沒有資料,使用「數字清單 1」右側資料
            median_num_right = nums_list_1[nums_list_1_median_partition_index]
        else:
            # 「數字清單 1」與「數字清單 2」有超過一個數字,有自己的中位數,取兩個右側中位數最小的那一個
            median_num_right = min(nums_list_1[nums_list_1_median_partition_index],
                                   nums_list_2[nums_list_2_median_partition_index])

        # 計算中位數左右平均
        median_num = float((median_num_left + median_num_right) / 2.0)

        return median_num


if __name__ == '__main__':
    # begin
    s = Solution()
    print(s.findMedianSortedArrays([1], [2, 3, 4, 5, 6]))
    print(s.findMedianSortedArrays([4], [1, 2, 3, 5, 6]))
    print(s.findMedianSortedArrays([], [1, 2, 3, 5, 6]))

參考資料