力扣-4 寻找两个正序数组的中位数

本文主要是介绍力扣-4 寻找两个正序数组的中位数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

转载自力扣题解https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/xun-zhao-liang-ge-you-xu-shu-zu-de-zhong-wei-s-114/
看到log的时间复杂度，会想起使用二分查找的方法，但是想不到题解给出的步骤，特此记录一下。
解题的关键在于：
1、将题目转换为求两个list中第k小的值；
2、利用二分法，依次找到前k-1个小的值，并将这些值“删除”，那么新数组的第1个值，就是我们想要找的第k个值！

class Solution:def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:# log时间复杂度，二分查找# 目的：找到两个数组中第k小的数m, n = len(nums1), len(nums2)totalLength = m + ndef getKthElement(k):                                # 注意k从1开始index1, index2 = 0, 0                            # 新数组的位置while True:# 特殊情况if index1 == m:                              # 第一个数组nums1已经遍历完毕，没发现目标值return nums2[index2 + k - 1]if index2 == n:                              # 第二个数组nums2已经遍历完毕，没发现目标值return nums1[index1 + k - 1]if k == 1:return min(nums1[index1], nums2[index2])# 正常情况newIndex1 = min(index1 + k // 2 - 1, m - 1)  # 防止越界newIndex2 = min(index2 + k // 2 - 1, n - 1)  # 防止越界pivot1, pivot2 = nums1[newIndex1], nums2[newIndex2]if pivot1 <= pivot2:k -= newIndex1 - index1 + 1              # 由于前newIdex1-index1+1个数肯定不是第k小的数，因此将其筛选出去，更新k的值index1 = newIndex1 + 1                   # 将前newIdex1-index1+1个数筛选出去之后，更新后边数组的索引else:k -= newIndex2 - index2 + 1index2 = newIndex2 + 1if totalLength % 2 == 1:return getKthElement((totalLength + 1) // 2)else:return (getKthElement(totalLength // 2) + getKthElement(totalLength // 2 + 1)) / 2

这篇关于力扣-4 寻找两个正序数组的中位数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---