【打卡贴】（No.004）从零开始刷LeetCode
击上方“Ahab杂货铺”，选择“置顶公众号”
技术分享第一时间送达！
NO.4两个排序数组的中位数
原题：
给定两个大小为 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中间数就是一组数据中中间的那个数。对于有限的数集，可以通过把所有观察值高低排序后找出正中间的一个作为中间数。题目其实挺良心是一个有序数组，如果对数据先排序，然后再进行取中值，则比较耗时。
这是从网上看到的一种快速提取中位数的算法：
1：取队首，队尾和中间的三个数，通过交换数据，使得队尾最大，中间的数据最小，队首的数据为哨兵。
2：交换中间和第2个数据，通过变换数据，使存在一个位置A，在该位置前的数据都小于哨兵，在该位置后的数据都大于或等于哨兵。
3：如果A的位置在队中之后，则更新队列为1~A，否则为A~end。并继续调用这个过程。
举例如下：
数组：3，6，2，1，9，8，0，4，5，7
经过步骤1并交换中间和第2个数的值之后，则为：
7，3，2，1，6，8，0，4，5，9；此序列中，7为哨兵
经过第一次迭代后，序列为：
4，3，2，1，6，5，0，7，8，9，此序列中，在数字7的位置是正确的。
第二次迭代则取1~7个数进行求解中位数，其中，哨兵为1。迭代之后如下：
0，1，2，3，6，5，4，7，8，9，同样的，此序列中，数字1的位置也是正确的。
第三次迭代则以第3~7个数进行求解，哨兵为5，此时，5即为中位数。
自己的解答从这种算法中的得到启发，但是写起来还是费劲一番周折。
代码如下：
# 判断传入数组是否为空
if nums1 is None or nums2 is None:
return
# 求出数组nums1、nums2的长度
nums1_length = len(nums1)
nums2_length = len(nums2)
# 求出两个数组的总长度
total_length = nums1_length + nums2_length
# 判断是否小于0
if total_length == 0:
return
# 如果数组nums2传入为空，则重新调用查询中位数，
# 调换参数位置，数组nums1的位置是允许为空的
if nums2_length == 0:
return self.findMedianSortedArrays(nums2, nums1)
left = -1
right = -1
nums1_Start = 0
nums2_Start = 0
# 循环遍历总长度一半，+1是因为range取不到总长度一半
for i in range(int(total_length/2)+1):
# left记录上一次循环的right值
left = right
# 如果nums1的记录点小于nums1的长度
# 并(nums2的记录点大于等于nums2的长度
# 或 nums1的记录点的值 小于 nums2记录点的值)
if nums1_Start < nums1_length and (nums2_Start >= nums2_length or nums1[nums1_Start] < nums2[nums2_Start]):
# 给right赋值 nums1的记录点的值，然后让nums1记录点加1
right = nums1[nums1_Start]
nums1_Start += 1
else:
# 给right赋值 nums2的记录点的值，
# 然后让nums2记录点加1
right = nums2[nums2_Start]
nums2_Start += 1
# 如果总长度 & 1 为 0 ，则使用两个数除2，
# 即判断total_length是否为偶数
# 也可使用total_length % 2 == 0这种判断，
# 但是使用&号性能稍高一点
if (total_length & 1) == 0:
return (left+right)/2.0
else:
# 使用除于1.0是为了让结果为浮点数
return right/1.0
以上的代码里已经添加了十分详细的注释，应该不难于理解，自己是不满意这段代码的，代码量很大，写起来很麻烦（毕竟自己比较懒）。
下面的代码是看到解答里代码量比较少的，但是执行速度稍微慢一点，其实这种方法自己并不是很懂，希望有小伙伴可以在留言区，说明思路。
tmp = nums1 + nums2
tmp.sort()
print (tmp)
if len(tmp)%2==1:
return tmp[int(len(tmp)/2)]
else:
return (tmp[int(len(tmp)/2)-1]+tmp[int(len(tmp)/2)])/2.0