原題地址：https://oj.leetcode.com/problems/median-of-two-sorted-arrays/

題意：There are two sorted arrays A and B 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)).

解題思路：這道題要求兩個已經(jīng)排好序的數(shù)列的中位數(shù)。中位數(shù)的定義：如果數(shù)列有偶數(shù)個數(shù)，那么中位數(shù)為中間兩個數(shù)的平均值；如果數(shù)列有奇數(shù)個數(shù)，那么中位數(shù)為中間的那個數(shù)。比如{1，2，3，4，5}的中位數(shù)為3。{1，2，3，4，5，6}的中位數(shù)為（3+4）/ 2 = 3.5。那么這題最直接的思路就是將兩個數(shù)列合并在一起，然后排序，然后找到中位數(shù)就行了。可是這樣最快也要O((m+n)log(m+n))的時間復雜度，而題目要求O(log(m+n))的時間復雜度。這道題其實考察的是二分查找，是《算法導論》的一道課后習題，難度還是比較大的。

　　　　 ? 首先我們來看如何找到兩個數(shù)列的第k小個數(shù)，即程序中getKth(A, B , k)函數(shù)的實現(xiàn)。用一個例子來說明這個問題：A = {1，3，5，7}；B = {2，4，6，8，9，10}；如果要求第7個小的數(shù)，A數(shù)列的元素個數(shù)為4，B數(shù)列的元素個數(shù)為6；k/2 = 7/2 = 3，而A中的第3個數(shù)A[2]=5；B中的第3個數(shù)B[2]=6；而A[2]<B[2]；則A[0]，A[1]，A[2]中必然不可能有第7個小的數(shù)。因為A[2]<B[2]，所以比A[2]小的數(shù)最多可能為A[0], A[1], B[0], B[1]這四個數(shù)，也就是說A[2]最多可能是第5個大的數(shù)，由于我們要求的是getKth(A, B, 7)；現(xiàn)在就變成了求getKth(A', B, 4)；即A' = {7}；B不變，求這兩個數(shù)列的第4個小的數(shù)，因為A[0]，A[1]，A[2]中沒有解，所以我們直接刪掉它們就可以了。這個可以使用遞歸來實現(xiàn)。

代碼：

class Solution:# @return a float# @line20 must multiply 0.5 for return a float else it will return an intdef getKth(self, A, B, k):lenA = len(A); lenB = len(B)if lenA > lenB: return self.getKth(B, A, k)if lenA == 0: return B[k - 1]if k == 1: return min(A[0], B[0])pa = min(k/2, lenA); pb = k - paif A[pa - 1] <= B[pb - 1]:return self.getKth(A[pa:], B, pb)else:return self.getKth(A, B[pb:], pa)def findMedianSortedArrays(self, A, B):lenA = len(A); lenB = len(B)if (lenA + lenB) % 2 == 1: return self.getKth(A, B, (lenA + lenB)/2 + 1)else:return (self.getKth(A, B, (lenA + lenB)/2) + self.getKth(A, B, (lenA + lenB)/2 + 1)) * 0.5

?

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結

以上是生活随笔為你收集整理的[leetcode]Median of Two Sorted Arrays @ Python的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。