专栏首页五分钟学算法这道算法题太简单?你忽略了时间复杂度的要求!

这道算法题太简单?你忽略了时间复杂度的要求!

点击蓝色“五分钟学算法”关注我哟

加个“星标”,天天中午 12:15 ,一起学算法

这道题目很有意思!

忽略时间复杂度的要求的话,so easy !加上了时间复杂度的要求,so hard!

而很多小伙伴一开始没有注意时间复杂度的要求,还很纳闷:这个难度是困难吗?怎么感觉比简单难度的的还简单啊。

题目来源于 LeetCode 上第 4 号问题:寻找两个有序数组的中位数。题目难度为 Hard,目前通过率为 35.6% 。

题目描述

给定两个大小为 mn 的有序数组 nums1nums2

请你找出这两个有序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1nums2 不会同时为空。

示例 1:

nums1 = [1, 3]
nums2 = [2]

则中位数是 2.0

示例 2:

nums1 = [1, 2]
nums2 = [3, 4]

则中位数是 (2 + 3)/2 = 2.5

题目解析

题目说的是给两个排好序的数组,让你求出这两个数组中所有元素按从小到大排列,排在中间的元素,时间复杂度也是有要求的,O(log(m + n)),m 和 n 分别是这两个数组的长度。

这里提到了时间复杂度为 O(log(m+n)) ,很容易想到的就是二分查找,所以现在要做的就是在两个排序数组中进行二分查找

具体思路如下,将问题 转化为在两个数组中找第 K 个小的数

求中位数,其实就是求第 k 小数的一种特殊情况。

首先在两个数组中分别找出第 k/2 大的数,再比较这两个第 k/2 大的数,这里假设两个数组为 A ,B。

那么比较结果会有下面几种情况:

  • A[k/2] = B[k/2],那么第 k 大的数就是 A[k/2]
  • A[k/2] > B[k/2],那么第 k 大的数肯定在 A[0:k/2+1] 和 B[k/2:] 中,这样就将原来的所有数的总和减少到一半了,再在这个范围里面找第 k/2 大的数即可,这样也达到了二分查找的区别了。
  • A[k/2] < B[k/2],那么第 k 大的数肯定在 B[0:k/2+1]和 A[k/2:] 中,同理在这个范围找第 k/2 大的数就可以了。

举个例子:

A = [1,3,4,7]
B = [1,2,3,4,5,6,7,8,9,10]

这两个数组总共 14 个数字,是偶数,因此要找出它们的第 15 / 2 = 7 小的数字与第 16 / 2 = 8 小的数字 。

下面以找出第 7 小的数字为例进行说明。

k = 7

k / 2 = 3

分别找出它们的第 k/2 大的数为 43 。(注意的是如果 k 是奇数,则向下取整)

根据这两个数将 A、B 数组划分为两部分。

然后对比这两个数,上边数组中的 4 和下边数组中的 3,如果哪个小,就表明该数组的前 k/2 个数字都不是第 k 小数字,可以舍弃。

舍弃掉的那三个数字肯定是在 最前面 的数字,因此一开始是要查找第 7 小的数字,现在变成了要查找第 7 - 3 = 4 小的数字。

同样的进行取两个数组的 k/2 数字进行区域划分与比较。

舍弃掉 A 数组的前部分之后,两个数组又发生了变化。

现在变成了去查找第 4 - 2 = 2 小的数字了。

此时出现了一个 特殊情况 :A 数组的 分割元素 与 B数组的 分割元素 相等,都为 4。

这种情况随意舍弃一个就行!代码编写的时候注意边界判断即可。

舍弃之后,问题简单了:查找两个数组中最小的那个数字。

只需要比较两个数组的开头数字就行了。(别忘记,这两个数组都是递增有序的)

所以第 7 小的数字是 4 。

同样的操作,可以查找出第 8 小的数字是 5。

所以,A 数组和 B 数组的中位数是 (4 + 5)÷ 2 = 4.5

如果你对上面的图片描述还是有点疑惑的话,强烈建议将下面的动画完整的看完。

动画描述

代码实现

//@author:windliang
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int n = nums1.length;
    int m = nums2.length;
    int left = (n + m + 1) / 2;
    int right = (n + m + 2) / 2;
    //一个小技巧:将偶数和奇数的情况合并,如果是奇数,会求两次同样的 k 。
    return (getKth(nums1, 0, n - 1, nums2, 0, m - 1, left) + getKth(nums1, 0, n - 1, nums2, 0, m - 1, right)) * 0.5;  
}

    private int getKth(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int k) {
        int len1 = end1 - start1 + 1;
        int len2 = end2 - start2 + 1;
        //让 len1 的长度小于 len2,这样就能保证如果有数组空了,一定是 len1 
        if (len1 > len2) return getKth(nums2, start2, end2, nums1, start1, end1, k);
        if (len1 == 0) return nums2[start2 + k - 1];

        if (k == 1) return Math.min(nums1[start1], nums2[start2]);

        int i = start1 + Math.min(len1, k / 2) - 1;
        int j = start2 + Math.min(len2, k / 2) - 1;

        if (nums1[i] > nums2[j]) {
            return getKth(nums1, start1, end1, nums2, j + 1, end2, k - (j - start2 + 1));
        }
        else {
            return getKth(nums1, i + 1, end1, nums2, start2, end2, k - (i - start1 + 1));
        }
    }

复杂度分析

时间复杂度:每进行一次循环,减少 k/2 个元素,所以时间复杂度是 O(log(k),而 k = (m+n) / 2,所以最终的复杂也就是 O(log(m+n)。

空间复杂度:虽然用到了递归,但是可以看到这个递归属于尾递归,所以编译器不需要不停地堆栈,所以空间复杂度为 O(1)。

References

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

: https://leetcode.wang/leetCode-4-Median-of-Two-Sorted-Arrays.html


本文相关阅读推荐:

毕业十年后,我忍不住出了一份程序员的高考试卷

一道腾讯面试题:厉害了我的杯

十大经典排序算法动画与解析,看我就够了!(配代码完全版)

这或许是东半球分析十大排序算法最好的一篇文章

面试官,我会写二分查找法!对,没有 bug 的那种!

看《长安十二时辰》可以了解哪些算法知识

GitHub 标星 3w+,很全面的算法和数据结构知识

本文分享自微信公众号 - 五分钟学算法(CXYxiaowu),作者:程序员小吴

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-08-08

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 冰与火之歌:「时间」与「空间」复杂度

    算法(Algorithm)是指用来操作数据、解决程序问题的一组方法。对于同一个问题,使用不同的算法,也许最终得到的结果是一样的,比如排序就有前面的十大经典排序和...

    五分钟学算法
  • 看动画轻松理解时间复杂度(二)

    上篇文章讲述了与复杂度有关的大 O 表示法和常见的时间复杂度量级,这篇文章来讲讲另外几种复杂度: 递归算法的时间复杂度(recursive algorithm ...

    五分钟学算法
  • LeetCode 图解 | 88. 合并两个有序数组

    题目来源于 LeetCode 上第 88 号问题:合并两个有序数组。题目难度为 Easy。

    五分钟学算法
  • 88合并两个有序数组

    给你两个有序整数数组 nums1 和 nums2,请你将 nums2 合并到 nums1 中,使 nums1 成为一个有序数组。

    宇宙之一粟
  • LeetCode-4. 两个排序数组的中位数(详解)

    链接:https://leetcode-cn.com/problems/median-of-two-sorted-arrays/description/ 有两...

    张诺谦
  • [LeetCode]Merge Sorted Array 合并排序数组 [LeetCode]Merge Sorted Array 合并排序数组

    链接:https://leetcode.com/problems/merge-sorted-array/description/ 难度:Easy 题目:88...

    尾尾部落
  • Leetcode#88. Merge Sorted Array(合并两个有序数组)

    给定两个有序整数数组 nums1 和 nums2,将 nums2 合并到 nums1 中,使得 num1 成为一个有序数组。

    武培轩
  • 【LeetCode题解-004】Median of Two Sorted Arrays

    There are two sorted arrays nums1 and nums2 of size m and n respectively.

    周三不加班
  • LeetCode 496. 下一个更大元素 I(哈希)

    给定两个没有重复元素的数组 nums1 和 nums2 ,其中nums1 是 nums2 的子集。找到 nums1 中每个元素在 nums2 中的下一个比其大的...

    Michael阿明
  • LeetCode - 两个数组的交集

    原题地址:https://leetcode-cn.com/problems/intersection-of-two-arrays/

    晓痴

扫码关注云+社区

领取腾讯云代金券