Leetcodeアルゴリズム-4、2つの秩序配列の中位数
タイトル
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.
配列(昇順)された配列nums 1とnums 2が2つあり、大きさはそれぞれmとnである.2つの配列の中位数を見つける必要があります.時間的複雑度はO(log(m+n))である必要がある.2つの配列が同時に空になることはありません.
例:Example 1:nums 1=[1,3]nums 2=[2]The median is 2.0
Example 2: nums1 = [1, 2] nums2 = [3, 4] The median is (2 + 3)/2 = 2.5
構想
2つの配列は秩序正しく、集計ソートを思い出しました.2つのシーケンスを組み合わせてソートするには、2つのポインタで2つの配列をそれぞれスキャンし、ポインタ+1のたびにサイズを比較する必要があります.この問題は直接集計ソートを用いて中位数を見つけることができるが,この複雑さはO(m+n)であり,条件を満たさない.この問題は中位数を見つけるだけで、他の要素がソートされるかどうかは重要ではありません.そのため、2つのポインタは毎回+1する必要はありません.毎回最適な値を追加して、全体の複雑さを最小限に抑えます.この適切な値は,一般に終点までの数ビットの半分に等しいので,複雑度はO(log(m+n))である.
python実装
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.
配列(昇順)された配列nums 1とnums 2が2つあり、大きさはそれぞれmとnである.2つの配列の中位数を見つける必要があります.時間的複雑度はO(log(m+n))である必要がある.2つの配列が同時に空になることはありません.
例:Example 1:nums 1=[1,3]nums 2=[2]The median is 2.0
Example 2: nums1 = [1, 2] nums2 = [3, 4] The median is (2 + 3)/2 = 2.5
構想
2つの配列は秩序正しく、集計ソートを思い出しました.2つのシーケンスを組み合わせてソートするには、2つのポインタで2つの配列をそれぞれスキャンし、ポインタ+1のたびにサイズを比較する必要があります.この問題は直接集計ソートを用いて中位数を見つけることができるが,この複雑さはO(m+n)であり,条件を満たさない.この問題は中位数を見つけるだけで、他の要素がソートされるかどうかは重要ではありません.そのため、2つのポインタは毎回+1する必要はありません.毎回最適な値を追加して、全体の複雑さを最小限に抑えます.この適切な値は,一般に終点までの数ビットの半分に等しいので,複雑度はO(log(m+n))である.
python実装
# -*- coding: utf-8 -*-
def findMedianSortedArrays(nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: float
：
， ： ， ， +1 。
， ， O(m+n)， 。
， ， ， +1， ， 。
"""
def fun_rec(nums1, i, nums2, j, k):
'''
i+j+k 。 i j ， k 。
'''
#
if i == len(nums1):
return nums2[j+k-1]
if j == len(nums2):
return nums1[i+k-1]
if k == 1:
return min(nums1[i], nums2[j])
# ， ，
if len(nums1) - i > len(nums2) - j:
return fun_rec(nums2, j, nums1, i, k)
# i j ， k/2， ， ， 。
ii = i + int(k/2)
ii = min(ii, len(nums1)) #
jj = i+j+k-ii # (ii-i)+(jj-j) == k， ii jj k， ， k
if nums1[ii-1] == nums2[jj-1]: # ， k
return nums1[ii-1]
if nums1[ii-1] < nums2[jj-1]: # ， k ， ii
return fun_rec(nums1, ii, nums2, j, k+i-ii) # fun_rec 2、4、5 i+j+k
return fun_rec(nums1, i, nums2, jj, k+j-jj)
#
total = len(nums1) + len(nums2)
if total % 2 == 1: # ，
return fun_rec(nums1, 0, nums2, 0, int((total+1)/2))
else: # ，
return (fun_rec(nums1, 0, nums2, 0, int(total/2)) + fun_rec(nums1, 0, nums2, 0, int(total/2+1))) / 2
def findMedianSortedArrays2(nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: float
， ， ， 。
： fun_rec k k k+1 。
"""
def fun_rec(nums1, i, nums2, j, k):
'''
i+j+k 。 i j ， k 。
'''
#
if i == len(nums1):
return (nums2[j+k-1], nums2[j+k])
if j == len(nums2):
return (nums1[i+k-1], nums1[i+k])
if k == 1:
if nums1[i] < nums2[j]:
return (nums1[i], find_next(nums1, i, nums2, j-1))
else:
return (nums2[j], find_next(nums2, j, nums1, i-1))
# ， ，
if len(nums1) - i > len(nums2) - j:
return fun_rec(nums2, j, nums1, i, k)
# i j ， k/2， ， ， 。
ii = i + int(k/2)
ii = min(ii, len(nums1)) #
jj = i+j+k-ii # (ii-i)+(jj-j) == k， ii jj k， ， k
if nums1[ii-1] == nums2[jj-1]: # ， k
return (nums1[ii-1], find_next(nums1, ii-1, nums2, jj-1))
if nums1[ii-1] < nums2[jj-1]: # ， k ， ii
return fun_rec(nums1, ii, nums2, j, k+i-ii) # fun_rec 2、4、5 i+j+k
return fun_rec(nums1, i, nums2, jj, k+j-jj)
def find_next(nums1, i, nums2, j):
'''
nums1 i，nums2 j。
nums1[i] 。
'''
if i == len(nums1) - 1:
return nums2[j+1]
return min(nums1[i+1], nums2[j+1])
#
if len(nums1)== 0 and len(nums2) == 1:
return nums2[0]
if len(nums2)== 0 and len(nums1) == 1:
return nums1[0]
total = len(nums1) + len(nums2)
result = fun_rec(nums1, 0, nums2, 0, int((total+1)/2))
if total % 2 == 1: # ，
return result[0]
else: # ，
return (result[0]+result[1])/2
if '__main__' == __name__:
nums1 = [1, 3]
nums2 = [2]
print(findMedianSortedArrays2(nums1, nums2))
nums1 = [1, 2]
nums2 = [3, 4]
print(findMedianSortedArrays2(nums1, nums2))