@author: ZZQ
@software: PyCharm
@file: findMedianSortedArrays.py
@time: 2018/10/10 19:24
说明：给定两个大小为 m 和 n 的有序数组 nums1 和 nums2 。请找出这两个有序数组的中位数。要求算法的时间复杂度为 O(log (m+n)) 。你可以假设 nums1 和 nums2 不同时为空。
示例 1: nums1 = [1, 3] nums2 = [2] 中位数是 2.0
示例 2: nums1 = [1, 2] nums2 = [3, 4] 中位数是 (2 + 3)/2 = 2.5
思路：空间换时间。首先判断合并后的数组奇偶，然后开辟新的空间l3来存放合并后的数据元素，存放到中位种停止，l3的最后一个元素就是中位数。
或者，用两个指针来存放中位数和中位数上一个元素的值，不断向前直至找到中位数。
class Solution(object):
def findMedianSortedArrays(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: float
"""
n = len(nums1)
m = len(nums2)
if (n+m) % 2 == 0:
flag = True
else:
flag = False
middle_index = (n + m) / 2 + 1
nums1_index, nums2_index = 0, 0
l3 = []
while nums1_index < n and nums2_index < m:
if nums1[nums1_index] > nums2[nums2_index]:
l3.append(nums2[nums2_index])
nums2_index += 1
else:
l3.append(nums1[nums1_index])
nums1_index += 1
if len(l3) == middle_index:
break
while nums1_index < n and nums2_index == m:
if len(l3) == middle_index:
break
l3.append(nums1[nums1_index])
nums1_index += 1
if len(l3) == middle_index:
break
while nums2_index < m and nums1_index == n:
if len(l3) == middle_index:
break
l3.append(nums2[nums2_index])
nums2_index += 1
if flag:
middle_value = (l3[len(l3)-2] + l3[len(l3)-1])/2.0
else:
middle_value = l3[len(l3)-1]
return middle_value