本文共 6212 字，大约阅读时间需要 20 分钟。

: https://www.bilibili.com/video/BV1hk4y1B74M/

题目

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

思路

暴力思路: 将两个数组先合并,再求中位数

class Solution:    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:        nums = sorted(nums1+nums2)        num_count = len(nums)                if num_count%2==1:            return nums[int((num_count-1)/2)]        else:            return (nums[int(num_count/2)-1] + nums[int(num_count/2)])/2

时间复杂度: O((m+n)log(m+n))

暴力思路2: 将所有元素分为两部分

将nums1和nums2两个数组各自分为较小的一半和较大的一半.然后将每个数组的两部分各自组合,若两部分正好能将整个集合二分,则中位数必然产生于两个数组各自的分割点附近.

我们希望,有x2<=y6且y5<=x3时,中位数发生于x2,x3,y5,y6之间,根据总元素数目:

• 若len(nums1)+len(nums2)为偶数,则中位数为avg(max(x2,y5)+min(x3,y6)).
• 若len(nums1)+len(nums2)为奇数,则中位数为max(x2,y5).

尝试次数	1	2	3	4
造型

有两个问题:

1. partition1和partition2之间满足什么约束条件?

2. 如何寻找partition1和partition2?

3. 边界情况: 若partition分割点正好为数组的首或尾时怎么办?

解:

1. partition1+partition2 == (len(nums1)+len(nums2)+1)/2:

   • 若len1=6,len2=8(总长度为偶数),则partition1+partition2=7.
   • 若len1=6,len2=7(总长度为奇数),则partition1+partition2=7.

   

2. 将partition1在较短的数组上滑动,根据partition1与partition2的约束关系,求出partition2.

   为什么partition1要在较短的数组上滑动?为了partition2永远能取到值.

   • 考虑一个极端的情况,在下图中,若根据nums2上的partition1为6时,nums1上的partition2的取值应该是多少?
   • 若根据长数组上的分割点来确定短数组上的分割点,必然带来类似问题: 长数组上的分割点取到某值时,短数组上取不到对应的分割点,这给长数组的遍历带来了麻烦.

   

3. 边界条件: 若分割点取到了数组的首或尾时怎么办

   根据数组的有序性在数组两侧添加虚拟的-∞和+∞.(不需要物理添加,只需要逻辑上添加)

   

   在实际编程中,我们可以通过min,max运算确保添加入数组的-∞和+∞不会真正地参与到中位数的产生过程中.

代码

class Solution {       public double findMedianSortedArrays(int[] nums1, int[] nums2) {   		// 必须在较小的数组上尝试partition1的取值,因此对两个数组进行交换        if (nums1.length > nums2.length) {               return findMedianSortedArrays(nums2, nums1);        }        int len1 = nums1.length;        int len2 = nums2.length;        for (int partition1 = 0; partition1 <= len1; partition1++) {   			// partition1在数组nums1上滑动, 根据partition1求出partition2            int partition2 = (len1 + len2 + 1) / 2 - partition1;            // 分别求出两个分割位置左右的值            int maxLeft1 = (partition1 == 0) ? Integer.MIN_VALUE : nums1[partition1 - 1];            int minRight1 = (partition1 == len1) ? Integer.MAX_VALUE : nums1[partition1];            int maxLeft2 = (partition2 == 0) ? Integer.MIN_VALUE : nums2[partition2 - 1];            int minRight2 = (partition2 == len2) ? Integer.MAX_VALUE : nums2[partition2];			// 若找到满足条件的分割方式,则求解中位数            if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {                   if ((len1 + len2) % 2 == 0) {                       return ((double) Math.max(maxLeft1, maxLeft2) + Math.min(minRight1, minRight2)) / 2;                } else {                       return (double) Math.max(maxLeft1, maxLeft2);                }            }        }        throw new IllegalArgumentException();    }    public static void main(String[] args) {           int[] nums1 = {   1, 3, 8, 9, 15};        int[] nums2 = {   7, 11, 19, 21, 23, 25};        Solution solution = new Solution();        System.out.println(solution.findMedianSortedArrays(nums1, nums2));    }}

时间复杂度: O(min(m,n))

二分法: 借助数组的有序性,减少尝试次数

数组有序性→二分法,这道题可以通过二分法来减小时间复杂度,具体来说,减少求取partition1的次数.

class Solution {       public double findMedianSortedArrays(int[] nums1, int[] nums2) {           if (nums1.length > nums2.length) {               return findMedianSortedArrays(nums2, nums1);        }        int len1 = nums1.length;        int len2 = nums2.length;		        // 分别定义了partition1取值的上下限        int low = 0;        int high = nums1.length;        while (low <= high) {               int partition1 = (low + high) / 2;            int partition2 = (len1 + len2 + 1) / 2 - partition1;            int maxLeft1 = (partition1 == 0) ? Integer.MIN_VALUE : nums1[partition1 - 1];            int minRight1 = (partition1 == len1) ? Integer.MAX_VALUE : nums1[partition1];            int maxLeft2 = (partition2 == 0) ? Integer.MIN_VALUE : nums2[partition2 - 1];            int minRight2 = (partition2 == len2) ? Integer.MAX_VALUE : nums2[partition2];			            if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {                   // 若找到符合条件的分割,则直接返回                if ((len1 + len2) % 2 == 0) {                       return ((double) Math.max(maxLeft1, maxLeft2) + Math.min(minRight1, minRight2)) / 2;                } else {                       return (double) Math.max(maxLeft1, maxLeft2);                }            } else if (maxLeft1 > minRight2) {               	// partiton1太靠右了,将区间向左倾斜                high = partition1 - 1;            } else {                   // partition1太靠左了,将区间向右倾斜                low = partition1 + 1;            }        }                throw new IllegalArgumentException();    }    public static void main(String[] args) {           int[] nums1 = {   1, 3, 8, 9, 15};        int[] nums2 = {   7, 11, 19, 21, 23, 25};        Solution solution = new Solution();        System.out.println(solution.findMedianSortedArrays(nums1, nums2));    }}

import mathclass Solution:    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:        if len(nums1) > len(nums2):            return self.findMedianSortedArrays(nums2, nums1)        left = 0        right = len(nums1)        sum_partition = int((len(nums1) + len(nums2)) / 2)        while (left <= right):            partition1 = int((left + right) / 2)            partition2 = sum_partition - partition1            left1 = -math.inf if partition1 == 0 else nums1[partition1-1]             right1 = math.inf if partition1 == len(nums1) else nums1[partition1]             left2 = -math.inf if partition2 == 0 else nums2[partition2-1]             right2 = math.inf if partition2 == len(nums2) else nums2[partition2]            if left1<=right2 and left2<=right1:                if (len(nums1)+len(nums2))%2 == 1:                    return min(right1, right2)                else:                    return (max(left1, left2) + min(right1, right2)) / 2            elif left2>right1:                left = partition1 + 1            else:                right = partition1 - 1        raise RuntimeError("程序出错")

时间复杂度: O(log(min(m,n)))

转载地址：http://hwhlz.baihongyu.com/