题目

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。 请你找出这两个有序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。 你可以假设 nums1 和 nums2 不会同时为空。

思路

竟然要求时间复杂度是O(log(m + n)),我能做出来就不错了,还要求这么高,要啥自行车啊,但是不管怎么样吧,先搞出来在说。至于时间复杂度,一步一步来吧。

解法一

首先我想的就是通过两个 index ,把两个数组合并成一个,然后取出来中间的一位或者两位,就是这个中位数。但是一想,其实没必要全部合并,只需要合并一半即可,虽然思路是正确的,可是最后却怎么也没写出来,总是有这样那样的问题,然后看解析,一个哥们和我是同样的思路,就搬了过来,

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int length = nums1.length + nums2.length;
    int mid = length / 2;
    int left = -1;
    int right = -1;
    int aStart = 0;
    int bStart = 0;
    for (int i = 0; i <= mid; i++) {
        //保存前一个数据
        left = right;
        //right始终取的就是两个数组中最小的那个,
        if (aStart < nums1.length && (bStart >= nums2.length || nums1[aStart] < nums2[bStart])) {
            right = nums1[aStart];
            aStart++;
        } else {
            right = nums2[bStart];
            bStart++;
        }
    }

    if (length % 2 == 0) {
        return (left + right) / 2.0;
    } else {
        return right;
    }
}
  1. 用的两个 index , aStart , bStart ,分别指向两个数组,
  2. 设置两个变量,用来存中间的两位
  3. 通过一个 for 循环,两个数组长度一半+1的长度,遍历两个数组,每次都是取个数组中最小的那个,然后index++;
  4. 如果长度是偶数,就是这两个变量平均数,如果是奇数,是这右侧变量的值。

学习的知识点: 之前我用了大量的代码处理边界的问题,是不是其中某个数组 num1 已经到底了,如果是的话,返回 num2 的值,如果不是,是不是 num2 到底了,如果是,返回 num1 的值,如果都没到边界,判断大小。。。等等一系列的判断,结果人家竟然又一句话就搞定了 aStart < nums1.length && (bStart >= nums2.length || nums1[aStart] < nums2[bStart])

  1. aStart < nums1.length 说明数组 nums1 没到底,
  2. bStart >= nums2.length   nums1[aStart] < nums2[bStart]
    • bStart >= nums2.length 说明数组 num2 到底了, 那么就返回 nums1 的值
    • nums1[aStart] < nums2[bStart] 返回最小的值,也就是 nums1 的值

满足条件一和二,就可以认为是返回 nums1 的值,否则就返回 nums2 的值。有点意思,记下了。 人家竟然能想出这么多方法,可是我想出来一个,却还没实现,代码写的不少,却总还是有问题,得好好练习才行

这个时间复杂度是O(m + n)。那O(log(m + n)) 的是什么样的呢,

解法二

其实看到O(log(m + n)) ,就应该的想起来递归,因为递归的时间复杂度就是O(log(n))的,但是却还是想不起来。可是牛人还是有的,一个哥们的代码,使用递归完美解决。而且这个还能处理另外一个问题,求两个有序数组的第 k 个数,如果 k 是中间值的时候,那么就是该问题的解。源码如下

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        //处理任何一个 nums 为空数组的情况
        if (m == 0) {
            if (n % 2 != 0)
                return 1.0 * nums2[n / 2];
            return (nums2[n / 2] + nums2[n / 2 - 1]) / 2.0;
        }
        if (n == 0) {
            if (m % 2 != 0)
                return 1.0 * nums1[m / 2];
            return (nums1[m / 2] + nums1[m / 2 - 1]) / 2.0;
        }
        int total = m + n;
        //总数为奇数,找第 total / 2 + 1 个数
        if ((total & 1) == 1) {
            return find_kth(nums1, 0 , nums2 , 0 , total / 2 + 1);
        }
        //总数为偶数,找第 total / 2 个数和第total / 2 + 1个数的平均值
        return (find_kth(nums1, 0 , nums2 , 0 , total / 2) + find_kth(nums1, 0 , nums2 , 0 , total / 2 + 1)) / 2.0;

    }

    //寻找 a 和 b 数组中,第 k 个数字
    double find_kth(int[] a, int a_begin , int[] b, int b_begin , int k) {
        //当 a 或 b 超过数组长度,则第 k 个数为另外一个数组第 k 个数
        if (a_begin >= a.length)
            return b[b_begin + k - 1];
        if (b_begin >= b.length)
            return a[a_begin + k - 1];
        //k为 1 时,两数组最小的那个为第一个数
        if (k == 1)
            return Math.min(a[a_begin], b[b_begin]);

        int mid_a = Integer.MAX_VALUE;
        int mid_b = Integer.MAX_VALUE;
        //mid_a / mid_b 分别表示 a 数组、b数组中第 k / 2 个数
        if (a_begin + k / 2 - 1 < a.length)
            mid_a = a[a_begin + k / 2 - 1];
        if (b_begin + k / 2 - 1 < b.length)
            mid_b = b[b_begin + k / 2 - 1];
        //如果 a 数组的第 k / 2 个数小于 b 数组的第 k / 2 个数,表示总的第 k 个数位于 a 的第k / 2个数的后半段,或者是 b 的第 k / 2个数的前半段
        //由于范围缩小了 k / 2 个数,此时总的第 k 个数实际上等于新的范围内的第 k - k / 2个数,依次递归
        if (mid_a < mid_b)
            return find_kth(a, a_begin + k / 2, b , b_begin , k - k / 2);
        //否则相反
        return find_kth(a, a_begin , b , b_begin + k / 2, k - k / 2);
    }

注释写的很清楚了,递归,我就想起来了之前看《数据结构与算法之美》的时候说的递归的三个条件

  • 一个问题可以分解为多个子问题的解
  • 这个问题分解后的子问题,除了数据规模之外,求解思路都是一样的
  • 存在递归终止条件

那么这个问题能分为多个子问题的解吗?
可以,分别求出 num1 , num2 两个数组的第k/2个元素的值 a , b ,然后判断 a 和 b 的大小,如果 a 大,则说明第 k 个元素在 num1 的[0,k/2]之间或者 num2 的[k/2,num2.length]之间,这样就排除了一半的元素,然后继续。执行这个方法,不过参数变化, num1 和 num2 的起始位置都需要变化,k的值也需要变化。第一次的时候是 k ,第二次的时候,因为已经排除掉了一半,那么 k 的值也需要减小一半,即k-k/2 这样除了数据规模之外,其他思路也都是一样的。条件二也满足了。

那条件三 终止条件呢?
肯定会有一个数组首先到头,那么就返回另外一个数组中第 k 个元素的值


路漫漫其修远兮,吾将上下而刷题。
— 搬运地址:

详细通俗的思路分析,多解法

真正O(log(m+n))的解法,那些说归并排序的别误导人了