题目:

给定两个大小为 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

演示动画

leetcode基础算法题100篇(动画演示LeetCode算法题)(1)

分析

寻找两个有序数组的中位数,我们能够很快的联想到使用二分法寻找一个有序数组的中位数,它的时间复杂度就是O(log(n))。现在是有两个数组,时间复杂度要求的是O(log(m n)),所以基本可以肯定就是和二分法有关了。

那么对于这个问题该如何使用二分发呢?我们进行进一步的分析。

既然是中位数,那么这个数的位置其实是可以确定的:

  • 对于m n为奇数的情况,中位数就是第(m n) / 2大的数。
  • 对于m n为偶数的情况,中位数就是第(m n) / 2大和第(m n) / 2 1大的数的平均数。

所以我们可以把上面的问题转换为寻找两个有序数组中第k大的数,k = (m n) / 2。

毫无疑问第k大的数有k1个来自于数组nums1,有k2个来自于数组nums2。由于k是确定的数,所以当k1确定的后,k2也就确定了。

所以我们可以在数组nums1中选一个k1,然后判断数组nums1的前k1个数和数组nums2的前k2个数是不是两个数组中最小的那一部分。判断条件为:

  1. nums1[k1 1] > nums[k2]
  2. nums2[k2 1] > nums[k1]

我们可以利用二分法来找这个k1。

实现代码:

leetcode基础算法题100篇(动画演示LeetCode算法题)(2)

,