4. 寻找两个正序数组的中位数
2021-03-17 本文已影响0人
简_爱SimpleLove
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
示例 1：
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2
示例 2：
输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
第一种方法
自己没看答案前，用Python自己的排序算法的做法，也是最简单的一种，但并不是最优的一种。
def findMedianSortedArrays1(nums1, nums2):
nums1.extend(nums2)
nums1.sort()
length = len(nums1)
if length%2 == 0:
return (nums1[int(length/2)] + nums1[int(length/2 -1)])/2.0
else:
return nums1[int((length - 1)/2)]
第二种方法
自己没看答案前，用自己的排序的数组，运行时间比用Python自己的排序算法运算时间少一点。但也还不最优的。
简单来说，用两个指针来分别记录每次读取到的数组角标。从第一个元素开始，每次比较两个数组的值，将小的那个值放入新的数组，然后将小的那个值所在数组记录的指针+1。最后如果有个数组先遍历完，就将另一个数组的剩余部分拼接在后面。
def findMedianSortedArrays2(nums1, nums2):
len1 = len(nums1)
len2 = len(nums2)
length = len1 + len2
# a用来记录nums1的角标，b用来记录nums2的角标
a, b = 0, 0
# 用来记录排序后的数组
total_nums = []
# 当nums1和nums2还没有遍历完过后，就继续遍历
while a < len1 or b < len2:
if a < len1 and b < len2:
# 当nums1中的数比nums2中的小，就添加nums1中的数，并且a+1
if nums1[a] < nums2[b]:
total_nums.append(nums1[a])
a += 1
# 当nums1中的数比nums2中的大或者等于，就添加nums2中的数，并且b+1
else:
total_nums.append(nums2[b])
b += 1
# 当nums1遍历完了过后，nums2还剩的有数据，就直接拼接在后面，并结束遍历
elif a == len1 and b < len2:
total_nums.extend(nums2[b:len2])
break
# 当nums2遍历完了过后，nums1还剩的有数据，就直接拼接在后面，并结束遍历
else:
total_nums.extend(nums1[a:len1])
break
# 如果排序后的总数组的长度是偶数，中位数就是中间两个数的平均值
# 如果总数组长度是奇数，中位数就是中间那个数
if length%2 == 0:
return (total_nums[int(length/2)] + total_nums[int(length/2 -1)])/2.0
else:
return total_nums[int((length - 1)/2)]
第三种方法
参考力扣官方答案，采用分割线和二分查找的方法如下（注释写的非常详细，相信你一定能看懂）：
"""
[2 4 6 | 15]
---
[1 7 | 8 10 17]
这里 7 为所求中位数
[3 8 | 9 10]
---
[2 4 6 | 12 18 20]
这里8 和 9的平均数为所求中位数
"""
def findMedianSortedArrays4(nums1, nums2):
# 为了使分割线在第二个数组两边都有元素，不至于下标越界，所以将较短的数组放在第一个
if len(nums1) > len(nums2):
nums1, nums2 = nums2, nums1
m = len(nums1)
n = len(nums2)
# 分割线左边的所有元素需要满足的个数 (m+n+1)/2
# 避免m+n整型溢出，写作 m + (n-m+1)/2
# 当m+n为奇数时，分割线使左边的元素个数比右边的元素个数多一个，中位数即为左边元素的最大值
totalLeft = m + int((n-m+1)/2)
# 在 nums1 的区间[0, m]里查找恰当的分割线
# 使得分割线左边的所有元素都小于等于分割线右边的所有元素
# 也就是使得nums1[i-1] <= nums2[j] && nums2[j-1] <= nums1[i]
left = 0
right = m
while left < right:
# nums1中中间元素的下标，即假设的分割线右边的下标
# 避免当只有两个元素的时候，进入死循环，所有需要在取中位数的时候括号里面 +1
# 因为在取中位数的时候括号里面 +1，所有i永远不会等于0，即下面的nums1[i-1]也不会越界
i = left + int((right - left + 1)/2)
# 对应的nums2中分割线右边的下标
j = totalLeft - i
# 分割线在第一个数组左边的数值严格大于分割线在第二个数组右边的数值
# 即是说分割线在第一个数组上的位置太靠右了，所有下一次查找的位置应该在i的左边
if nums1[i-1] > nums2[j]:
# 下一轮的搜索区间 [left, i-1]
right = i - 1
else:
# 是上一个搜索区间的反面区间
# 下一轮的搜索区间 [i, right]
# 当出现left = i时，就需要注意只有两个元素的时候，会进入死循环。
# 需要在取中位数的时候括号里面 +1
left = i
"""
上面的while循环等价于：
while left < right:
# 下面是left = i + 1，所以中位数的取值不需要向上取整，也就是不需要括号里面 +1
i = left + int((right - left)/2)
j = totalLeft - i
if nums2[j-1] > nums1[i]:
# 下一轮的搜索区间是 [i+1, right]
# 当看到 left = i + 1 这样的表达时，表示中位数的取值不需要向上取整，也就是不需要括号里面 +1
left = i + 1
else:
# 下一轮的搜索区间是 [left, i]
right = i
"""
# 当退出while循环的时候，也就是说找到了使得nums1[i-1] <= nums2[j] && nums2[j-1] <= nums1[i]
# 满足的left的位置，需要重新定义i和j
i = left
j = totalLeft - i
# 定义分割线左右两侧的四个元素
# 声明一个无穷大的数
infinty = 2 ** 40
# i == 0 时没有意义，将nums1LeftMax设置为最小值，让它在比较最大值的时候不被选中
# 即第一个数组的所有元素都在分割线的最右边，比如如下：
"""
数组[7 8 9]和[1 2 3 4 5]分割线如下：
nums1LeftMax | [7 8 9]
-----------
[1 2 3 4 | 5]
此时的i==0，第一个数组全部都在分割线的右边，将nums1LeftMax设置为一个无穷小的数
这样在和分割线右边比较的时候，就不会被选中
"""
nums1LeftMax = (-infinty if i == 0 else nums1[i-1])
# i == m 时没有意义，将nums1RightMin设置为最大值，让它在比较最小值的时候不被选中
# 即第一个数组的所有元素都在分割线的最左边
nums1RightMin = (infinty if i == m else nums1[i])
# j == 0 时没有意义，将nums2LeftMax设置为最小值，让它在比较最大值的时候不被选中
# 即第二个数组的所有元素都在分割线的最右边
nums2LeftMax = (-infinty if j ==0 else nums2[j-1])
# j == n 时没有意义，将nums2RightMin设置为最大值，让它在比较最小值的时候不被选中
# 即第二个数组的所有元素都在分割线的最左边
nums2RightMin = (infinty if j == n else nums2[j])
if (m+n)%2 == 1:
# 当两个数组的长度之和为奇数时，返回分割线左边的最大值
return max(nums1LeftMax, nums2LeftMax)
else:
# 当两个数组的长度之和为偶数时，返回分割线左边元素的最大值和右边元素最小值的平均数
leftMax = max(nums1LeftMax, nums2LeftMax)
rightMin = min(nums1RightMin, nums2RightMin)
return (leftMax + rightMin) / 2
第四种方法
参考力扣官方答案，采用分数组和二分查找的方法如下：
def findMedianSortedArrays3(nums1, nums2):
# 保证第一个数组的长度小于等于第二个数组的长度
if len(nums1) > len(nums2):
return findMedianSortedArrays3(nums2, nums1)
# 声明一个无穷大的数
infinty = 2 ** 40
# m 和 n 分别记录 nums1 和 nums2的长度
m, n = len(nums1), len(nums2)
# 用于二分查找的指针
left, right = 0, m
# median1：前一部分的最大值
# median2：后一部分的最小值
median1, median2 = 0, 0
while left <= right:
# 前一部分包含 nums1[0 .. i-1] 和 nums2[0 .. j-1]
# 后一部分包含 nums1[i .. m-1] 和 nums2[j .. n-1]
# // 表示 取整除 - 返回商的整数部分（向下取整）
i = (left + right) // 2
# 因为i表示nums1左边的元素个数，表示nums2左边的元素个数
# 所以i + j就等于两个数组总和的一半（如果两个数组的总和为奇数，保证左边比右边多一个）
j = (m + n + 1) // 2 - i
# nums_im1, nums_i, nums_jm1, nums_j 分别表示 nums1[i-1], nums1[i], nums2[j-1], nums2[j]
nums_im1 = (-infinty if i == 0 else nums1[i - 1])
nums_i = (infinty if i == m else nums1[i])
nums_jm1 = (-infinty if j == 0 else nums2[j - 1])
nums_j = (infinty if j == n else nums2[j])
# 在[0, m]中找到最大的i使得 nums1[i-1] <= nums2[j]时，就找到了正确的分割线
# 如果i是最大的，那么i+1将不满足。将i+1代入进去，也就是说 nums1[i] > nums2[j-1]
# 所以下一次的查找区间是[i+1, right]
if nums_im1 <= nums_j:
median1, median2 = max(nums_im1, nums_jm1), min(nums_i, nums_j)
left = i + 1
else:
right = i - 1
return (median1 + median2) / 2.0 if (m + n) % 2 == 0 else median1
复杂度分析
上面的第三种和第四种方法的复杂度如下：
- 时间复杂度：O(logmin(m,n)))，其中m 和 n 分别是数组 nums1和 nums2 的长度。查找的区间是 [0,m]，而该区间的长度在每次循环之后都会减少为原来的一半。所以，只需要执行 logm 次循环。由于每次循环中的操作次数是常数，所以时间复杂度为 O(logm)。由于我们可能需要交换 nums1 和 nums2使得 m≤n，因此时间复杂度是O(logmin(m,n)))。
- 空间复杂度：O(1)，只使用到常数个变量。
第五中方法
参考力扣官方答案，寻找两个数组中第k小的元素，就是需要找的中位数。这里查找的时候，就可以使用二分查找。在官方的基础上写了更加详细的注释，相信你能看懂，代码如下：
def findMedianSortedArrays5(nums1, nums2):
# 获取第k小的元素
def getKthElement(k):
"""
- 主要思路：要找到第 k (k>1) 小的元素，那么就取 pivot1 = nums1[k/2-1] 和 pivot2 = nums2[k/2-1] 进行比较
- 这里的 "/" 表示整除
- nums1 中小于等于 pivot1 的元素有 nums1[0 .. k/2-2] 共计 k/2-1 个
- nums2 中小于等于 pivot2 的元素有 nums2[0 .. k/2-2] 共计 k/2-1 个
- 取 pivot = min(pivot1, pivot2)，两个数组中小于等于 pivot 的元素共计不会超过 (k/2-1) + (k/2-1) <= k-2 个
- 这样 pivot 本身最大也只能是第 k-1 小的元素
- 如果 pivot = pivot1，那么 nums1[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除"，剩下的作为新的 nums1 数组
- 如果 pivot = pivot2，那么 nums2[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除"，剩下的作为新的 nums2 数组
- 由于我们 "删除" 了一些元素（这些元素都比第 k 小的元素要小），因此需要修改 k 的值，减去删除的数的个数
"""
# 用来分别记录两个数组的角标，默认都是从0开始
# 即角标比index1和index2小的元素，就都是比第k小的元素小的，也就是排除了下标范围的元素
index1, index2 = 0, 0
while True:
# 当nums1元素都排除完过后，需要找的第k小的元素就是nums2剩下还没排除下标范围的第k小元素
# 因为查找的是第k个元素，所以角标就是 k-1
# 因为nums2已经访问到index2了，所以剩下第k小元素的角标就是 index2+(k-1)
if index1 == m:
return nums2[index2 + (k - 1)]
# 和index1==m的情况同理
if index2 == n:
return nums1[index1 + (k - 1)]
# 当k的值变成1，比较两个有序数组中的未排除下标范围内的第一个数，其中较小的数即为第k个数
if k == 1:
return min(nums1[index1], nums2[index2])
# 二分查找就体现在这一步
# 每次循环查找，就比较两个数组中 未排除下标范围中的第k/2的数
# 因为未排除下标范围的数组是从index1开始的，所以对应的角标就是 index1+(k//2 -1)
# 为了避免数组越界，选取对应数组中的最后一个元素
newIndex1 = min(index1 + (k // 2 - 1), m -1)
# 和newIndex1同理
newIndex2 = min(index2 + (k // 2 - 1), n -1)
# pivot1和pivot2 分别记录nums1和nums2中排除下标范围中的第k/2的数
pivot1, pivot2 = nums1[newIndex1], nums2[newIndex2]
# 未排除下标范围的数组中 nums1中第k/2个数比nums2中第k/2个数小或者等于
if pivot1 <= pivot2:
"""
删除前：
A: 1 2 3 4 5 6 7 8 9
↑
B: 1 3 4 9
↑
删除后：
A: [1 2 3] 4 5 6 7 8 9
↑
B: 1 3 4 9
↑
需要删除的元素是： [1 2 3]
删除前A数组中：newIndex1 = 2 index1 = 0
删除后A数组中：index1 = newIndex1 + 1 = 3
"""
# newIndex1-index1 表示需要删除的元素个数
# 因为pivot1不大于pivot2，所以还需要删除本身，所以需要 +1
# 因为删除了这么多元素，所以对应的K也就减少这么多
k -= newIndex1 - index1 + 1
# 将nums1中的角标指向 还未排除的下标范围的第一个 （比如指向上面的4对应的角标）
index1 = newIndex1 + 1
else:
# 原理同上
k -= newIndex2 - index2 + 1
index2 = newIndex2 + 1
# 将m, n分别表示nums1和nums2的长度
m, n = len(nums1), len(nums2)
# 两个数组的总长度
totalLength = m + n
if totalLength%2 ==1:
# 如果totalLength为奇数，那么第 (totalLength + 1) // 2 小的数，即是中位数
return getKthElement((totalLength + 1) // 2)
else:
# 如果totalLength为偶数，那么第 totalLength // 2 小的数和第 totalLength // 2 + 1小的数的平均数，即是中位数
return (getKthElement(totalLength // 2) + getKthElement(totalLength // 2 + 1)) / 2.0
复杂度分析
- 时间复杂度：O(log(m+n))，其中 m 和 n 分别是数组 nums1和nums2的长度。初始时有 k=(m+n)/2 或 k=(m+n)/2+1，每一轮循环可以将查找范围减少一半，因此时间复杂度是 O(log(m+n))。
- 空间复杂度：O(1)，只使用到常数个变量。
