算法/编程练习：两个有序数组的中位数

本文主要是介绍算法/编程练习：两个有序数组的中位数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

算法/编程练习：两个有序数组的中位数

题目来自LeetCode:
https://leetcode-cn.com/problems/median-of-two-sorted-arrays/

题目：

给定两个大小为 n1 和 n2 的有序（升序）数组 nums1 和 nums2 ，
找出这两个有序数组的中位数mid。
要求算法的时间复杂度为 O(log(m + n))。
例如，
输入:  nums1 = [1, 3, 5, 7, 9],  nums2 = [2, 4, 6, 8, 10, 11]
输出:  mid=6

思路：

记总的数组长度为 N = n1 + n2，则两个数组中小于等于mid的数有 N_lef = int(N/2)个 。
假设用索引 idx1 将 nums1 分为左右两部分，用索引 idx2 将 nums2 分为左右两部分，
若此时 nums1 和nums2的左边部分共同构成 mid 的左边，
nums1 和 nums2 的右边部分共同构成 mid 的右边，
那么 idx1 和 idx2 应满足等量约束 idx2 + idx1 + 1 = N_left。
根据中位数的定义，nums1 左边部分的最大值不能大于 num2 右边部分的最小值，
nums2 的切分同理。
因此只需要从 nums1 的最大索引开始遍历，找出 合适的 idx1 和 idx2 即可。  即：
# idx1把nums1分为左右两部分：
nums1_left = nums1[0:idx1+1]
nums1_right = nums1[idx1+1:]
# idx2把nums2分为左右两部分：
nums2_left = nums2[0:idx2]
nums2_right = nums2[idx2:]
# 能正确划分nums1和nums2从而找到mid的idx1和idx2应满足
idx2 = N_left - (idx1+1) # 且
nums1[idx1] <= nums2[idx2]

Python代码：

def Find2OrderedListMid(nums1, nums2):if not isinstance(nums1, list) or not isinstance(nums2, list):print('请输入两个列表！')return Nonen1, n2 = len(nums1), len(nums2)N = n1 + n2N_left = int(N/2) # 合并数列中，中位数前面的数的个数odd = False if N % 2 == 0 else True# 代码简化处理，不考虑有数组长度为0的情况下if n1 == 0 or n2 == 0:print('需要保证两个数组的长度均大于0！')return None# 保持nums1的长度小于等于nums2if n1 > n2:nums1, nums2 = nums2, nums1n1, n2 = len(nums1), len(nums2)idx1 = n1-1idx2 = N_left - (idx1+1)# 注意这里idx2的最大取值为n2-1，原因在于限制了n1 <= n2while nums1[idx1] > nums2[idx2] and idx1 > -1 and idx2 < n2-1:idx1 -= 1idx2 += 1if odd:    # odd为True时有两种情况：nums1的数全分配到左边或左右都有# (由于odd为True时必有n1<n2，因此nums2的数不可能全部分配到左边)if idx1 == n1-1: # nums1的数全分配到左边mid = nums2[idx2]else:mid = min(nums1[idx1+1], nums2[idx2])else:# odd为False时计算左边部分最大值，有三种情况if idx1 == -1: # nums1的数全部分配到右边max_left = nums2[idx2-1]elif idx2 == 0: # nums2的数全部分配到右边max_left = nums1[idx1]else:max_left = max(nums1[idx1], nums2[idx2-1])# odd为False时计算右边最小值，有两种情况# （由于N为偶数且n1 <= n2，因此当nums2的数全部分配到左边时，实际上n1 == n2，#  计算中位数时也要取nums2最后一个值）if idx1 == n1-1: # nums1的数全分配到左边min_right = nums2[idx2]else:min_right = min(nums1[idx1+1], nums2[idx2])mid = (max_left + min_right) / 2return mid


if __name__ == '__main__':    nums1 = [1, 3, 5, 7, 9]nums2 = [2, 4, 6, 8, 10, 11]print(Find2OrderedListMid(nums1, nums2))