4. Median of Two Sorted Arrays
Leetcode 问题: 4. Median of Two Sorted Arrays
Categories:
题目
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]))