首页 > 代码库 > 【LeeetCode】4. Median of Two Sorted Arrays
【LeeetCode】4. Median of Two Sorted Arrays
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)).
Example 1:
nums1 = [1, 3] nums2 = [2] The median is 2.0
Example 2:
nums1 = [1, 2] nums2 = [3, 4] The median is (2 + 3)/2 = 2.5
题意:找出两个数组的中间值
思路:首先是想利用像归并排序的方法,排序完成后,选出中间值,但是时间复杂度就不是O(log(m+n))了
从网上找到另一种方法,我写下我自己理解的思路:
找出中间值,也就是找出第K小的数
借用二分查找法的思路,第k/2小的值在或者不在短的数组中,就比如短的数组事nums1。
如果k/2在短的数组中,就比较nums1[k/2]和nums2[k/2],比如如果nums1[k/2]更小,那么就可以排除掉nums1中,索引k/2之前的所有数。
如果k/2不在短的数组中,就比较nums1[len(nums1)]和nums2[k-len(nums1)]的值,谁更小,就排除掉哪个数组
如果两个值相等,就找到了!
1 class Solution(object): 2 def findMedianSortedArrays(self, nums1, nums2): 3 """ 4 :type nums1: List[int] 5 :type nums2: List[int] 6 :rtype: float 7 """ 8 len1 = len(nums1) 9 len2 = len(nums2) 10 l = len1 + len2 11 if l&0x1 == 1: 12 return self.findK(nums1,len1,nums2,len2,l/2+1) 13 else: 14 return (self.findK(nums1,len1,nums2,len2,l/2)+self.findK(nums1,len1,nums2,len2,l/2+1))*1.0/2 15 16 def findK(self,nums1,len1,nums2,len2,k): 17 if len1>len2: 18 return self.findK(nums2,len2,nums1,len1,k) 19 if len1 == 0: 20 return nums2[k-1] 21 if k == 1: 22 return min(nums1[0],nums2[0]) 23 mid = k/2 24 pa = min(mid,len1) 25 pb = k-pa 26 if nums1[pa-1] < nums2[pb-1]: 27 return self.findK(nums1[pa:],len1-pa,nums2,len2,k-pa) 28 elif nums1[pa-1] > nums2[pb-1]: 29 return self.findK(nums1,len1,nums2[pb:],len2-pb,k-pb) 30 else: 31 return nums1[pa-1]
【LeeetCode】4. Median of Two Sorted Arrays
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。