題目：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))
題解：
1、自己想得思路：構建一個list，然后比較各數的大小，將其插入到合適的位置
class Solution: # @param {integer[]} nums1 # @param {integer[]} nums2 # @return {float} def findMedianSortedArrays(self, nums1, nums2): nums = nums1[:] # 構建一個list，并將nums1的值賦給它 x = len(nums1) y = len(nums2) for i in range(x + y): if i < len(nums): if len(nums2) == 0: break # 如果nums2沒有數了就跳出 elif nums[i] < nums2[0]: continue else: # 否則將nums2[0]插入到i位置 num = nums2.pop(0) nums.insert(i, num) else: break nums.extend(nums2) n = len(nums)/2 # 輸出結果 if len(nums)%2 == 0: return (nums[n] + nums[n-1])/2.0 else: return nums[n]2、參考網上的解題思路（http://c4fun.cn/blog/2014/03/20/leetcode-solution-02/）
用求兩個有序數組的第K大數的方法：
假設A數組中取第X個數， B數組中取第Y個數，并且滿足X+Y=K， 若A[X] < B[Y]，則比A[X]小的數必然少于K個，也就是說A[1]到A[X]都比第K個數要小，可以舍棄掉然后求第K-X小的數，反之亦然
class Solution: def findMedianSortedArrays(self, A, B): totlen = len(A) + len(B) if (1 & totlen): # 通過位運算判斷奇偶數，nice return self.findK(A, B, (totlen+1)/2) else: return (self,findK(A, B, totlen/2) + self.findK(A, B, totlen/2+1))/2.0 def findK(self, A, B, K): la, lb, pa, pb = len(A), len(B), min(K/2, len(A)), K - (min(K/2, len(A))) if (la > lb): return self.findK(B, A, K) if (la == 0): return B[K-1] if (K == 1): return min(A[0], B[0]) if A[pa-1] < B[pb-1]: return self.findK(A[pa:], B, K-pa) elif A[pa-1] > B[pb-1]: return self.findK(A, B[pb:], K-pb) else: return A[pa-1]
新聞熱點
疑難解答
