题目：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]
新闻热点
疑难解答
