首页 > 代码库 > LeetCode题解 15题 第二篇
LeetCode题解 15题 第二篇
之前写过一篇，这是第二篇。上一篇用了多种编程语言来做，这一次是以学算法为主，所以打算都用python来完成。
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
这道题比较难，参考了这篇文章http://blog.csdn.net/yutianzuijin/article/details/11499917/，然后用python写了程序
其中第k小数算法是关键。总结下思路，争取以后我也可以多发明些这类nb的算法。
主要是将求A得问题巧妙地转换为求B的问题，并且在逻辑上证明是合理的。
class Solution(object): def findKth(self, arr1, len1, arr2, len2, k): #always assume that len1 is equal or smaller than len2 if len1 > len2: return self.findKth(arr2, len2, arr1, len1, k) if len1 == 0: return arr2[k - 1] if k == 1: return min(arr1[0], arr2[0]) #divide k into two parts pa = min(k / 2, len1) pb = k - pa if arr1[pa - 1] < arr2[pb - 1]: return self.findKth(arr1[pa:], len1 - pa, arr2, len2, k - pa) elif arr1[pa - 1] > arr2[pb - 1]: return self.findKth(arr1, len1, arr2[pb:], len2 - pb, k - pb) else: return arr1[pa - 1] def findMedianSortedArrays(self, nums1, nums2): """ :type nums1: List[int] :type nums2: List[int] :rtype: float """ nums1_len = len(nums1) nums2_len = len(nums2) total = nums1_len + nums2_len if total & 1: return self.findKth(nums1, nums1_len, nums2, nums2_len, total/2 + 1) else: ret1 = self.findKth(nums1, nums1_len, nums2, nums2_len, total/2) ret2 = self.findKth(nums1, nums1_len, nums2,nums2_len, total/2 + 1) return float((ret1 + ret2)) / 2
LeetCode题解 15题 第二篇
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。