困难题 找两个正序数组中的中位数

题目

给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？

示例：

输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

分析思路

如果要求 O(log (m+n)) 的时间复杂度，八成是需要通过二分法，或者内部具有树形结构的堆排序之类的算法做到的。

如果只局限于中位数，可能找不到什么方便的方法。但是中位数事实上就是第K大数的变体。总共有m+n个元素，那么只要找到(m+n)//2+1大的数（奇数个数的情况），或者找到排序(m+n)//2和(m+n)//2+1两个数再求均值（偶数个数的情况）即可。可以使用二分法来解决。

二分的关键在于，每次排除半数的情况，让结果可能所在的范围每次减半，就可以减小时间复杂度，节约时间开销。

本题中，由于两个数组都已经排好序，可以比较巧妙地采用这样的思维：如果比某数小的数肯定没有k-1这么多个，那么这个数，以及比它还小的数就不会是第k大的数。每次从前往后选出两个数列中下标为[k//2-1]的数进行比较，其中比较小的那个，他之前不会有超过k-2个数比它小，因此他不可能是第k大的数，所以可以把它和该数列中它之前的数（一定比它更小）排除掉。如果两个数相等，那么两个数总有一个不是第k大的数，因此可以归于任意一个小的情况里。这样每次就能排除k//2个数。重新计算k，然后从剩余的数中找新的第k大的数。

如果出现一个数列取第[k//2-1]个数越界的情况，就取最后一个数代替，但是排除的数的数量就不一定是k//2个了。

出现任意一种情况就结束迭代：

  1. 任意一个数列全部被排除，此时直接按照下标取另一数列中的k大数即可。
  2. k==1 此时取两个数列首元素的最小值即可。

示例代码

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        m, n = len(nums1), len(nums2)
        totalLength = m + n
        def getKthElement(k):
            index1, index2 = 0, 0
            while True:
                # 特殊情况 结束条件
                if index1 == m:
                    return nums2[index2 + k - 1]
                if index2 == n:
                    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
                    index1 = newIndex1 + 1
                else:
                    k -= newIndex2 - index2 + 1
                    index2 = newIndex2 + 1
                    
    if totalLength % 2 == 1:
        return getKthElement((totalLength + 1) // 2)
    else:
        return (getKthElement(totalLength // 2) + getKthElement(totalLength // 2 + 1)) / 2

其他题目

两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

你可以按任意顺序返回答案。

题解：如果要追求比较低的时间复杂度，可以使用哈希表的方法。本题只需要遍历一遍，到一个数a的时候找一下之前有没有出现过target-a即可。所以可以将沿途的数都加入哈希表，找起来会非常迅速。但是需要牺牲一定的空间。

启发：哈希表是一种常见的用高空间复杂度换取低时间复杂度的策略。

无重复的最长子串

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

题解：使用滑动窗口策略，从开头拉出窗口，如果tail拉不动了，就把head拉一下再尝试拉tail，记录把head从头拉到尾的过程中最大窗口长度即可。

注意：本题滑动窗口是O(n)时间复杂度，因为虽然有循环嵌套，但是第二层循环中的内容每次是从上次的基础上继续向后遍历，所以只会执行n次，O(n)复杂度。

另一题两数相加较为简单，不做记录。