刷题笔记数组二分法Leetcode4.寻找两个正序数组的中位数
赵海波
4. 寻找两个正序数组的中位数
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。
示例 1：
1
2
3
| >输入：nums1 = [1,3], nums2 = [2]
>输出：2.00000
>解释：合并数组 = [1,2,3] ，中位数 2
|
示例 2：
1
2
3
| >输入：nums1 = [1,2], nums2 = [3,4]
>输出：2.50000
>解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
|
困难题
目前还做不明白，只会先合并之后再取出中位数：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class Solution(object):
def findMedianSortedArrays(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: float
"""
nums = nums1+nums2
i,j,k = 0,0,0
while(i<len(nums1) and j <len(nums2)):
if (nums1[i]<=nums2[j]):
nums[k] = nums1[i]
k += 1
i += 1
else:
nums[k] = nums2[j]
k += 1
j += 1
while(i < len(nums1)):
nums[k] = nums1[i]
k += 1
i += 1
while(j < len(nums2)):
nums[k] = nums2[j]
k += 1
j += 1
return (nums[len(nums)/2]+nums[(len(nums)-1)/2])/2.0
|
