溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
Python尋找兩個有序數組的中位數
審題：
1.找出意味著這是一個查找算法題
2.算法復雜度log級別，就是提示你是二分查找
3.二分查找實現一般為遞歸
（1）遞歸包括遞歸體
（2）終止條件
思路：
定理：
1.有序數組中有一半的元素小于等于數組的中位數，有一半的元素大于等于中位數（如果數組中元素個數是奇數，那么這里的一半并不是嚴格意義的1/2）
2.如果我們去掉其中一個數組比中位數小的k個數，再去掉另一個數組中比中位數大的k個數，得到的合并子數組的中位數和原來的中位數相同。
eg：[1,2,3],[1,2,3] => [1,1,2,2,3,3]
根據定理去除元素[2,3],[1,2] => [1,2,2,3]中位數沒變。我用了特殊的例子解釋，你可以自行換一個試一試。如果兩個的數組長度不一樣的時候，不能去掉各自的一半，要去掉相同的個數，下面會細說
解題思路：
假設兩個數組的中位數分別是a[m1],b[m2]
1.if a[m1] == b[m2] ，那么剛好有一半的元素小于a[m1],那么a[m1]就是要找的中位數。參考上面的列子
2.if a[m1] < b[m2]，根據定理1可知，這個中位數只可能出現在a[n1/2 ~ n1-1]或者b[0 ~ n2/2].也就是說合并這兩個數組的中位數和原來的數組合并的數組的中位數是一樣的。 根據定理2可知：
1.數組長度一樣的時候，去除掉一半是合理的。
2.數組長度不一樣，這么做中位數可能發生變化。解決方案就是去除掉相同個數的元素。why？假設n1 < n2, 兩個數組就去掉n1/2個元素。那就不在是上面的范圍（a[n1/2 ~ n1-1]或者b[0 ~ n2/2]），而是a[n1/2 ~ n1-1]或者b[0 ~ (-n1/2+n2-1)].
結論就是：只能刪除a的n1/2(向下取整)
3.if a[m1] > b[m2],和上面分析類似，中位數只能出現在a的前半段或者b的后半段。也就是說a[0 ~ n1/2]和b[n1/2 ~ n2-1]的中位數和原來的中位數相同。
參考：LeetCode參考答案
class Solution:
def findMedianSortedArrays(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: float
"""
m, n = len(nums1), len(nums2)
if m > n:
nums1, nums2, m, n = nums2, nums1, n, m
if n == 0:
raise ValueError
imin, imax, half_len = 0, m, (m + n + 1) // 2
while imin <= imax:
i = (imin + imax) // 2
j = half_len - i
if i < m and nums2[j-1] > nums1[i]:
# i is too small, must increase it
imin = i + 1
elif i > 0 and nums1[i-1] > nums2[j]:
# i is too big, must decrease it
imax = i - 1
else:
# i is perfect
if i == 0: max_of_left = nums2[j-1]
elif j == 0: max_of_left = nums1[i-1]
else: max_of_left = max(nums1[i-1], nums2[j-1])
if (m + n) % 2 == 1:
return max_of_left
if i == m: min_of_right = nums2[j]
elif j == n: min_of_right = nums1[i]
else: min_of_right = min(nums1[i], nums2[j])
return (max_of_left + min_of_right) / 2.0
總結
以上所述是小編給大家介紹的Python尋找兩個有序數組的中位數，希望對大家有所幫助，如果大家有任何疑問請給我留言，小編會及時回復大家的。在此也非常感謝大家對億速云網站的支持！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
