专栏首页程序员管小亮的成长之路【手绘漫画】图解LeetCode之寻找重复数(LeetCode287题),抽屉原理

【手绘漫画】图解LeetCode之寻找重复数(LeetCode287题),抽屉原理

文章首发于本人CSDN账号:https://blog.csdn.net/tefuirnever

由于微信不允许外部链接,你需要点击页尾左下角的“阅读原文”,才能访问文中的链接。

1、前言

手绘漫画系列正式上线!!!"图解LeetCode刷题计划" 来了!!!

今天是第四期,争取每天一期,最多两天一期,欢迎大家监督我。。。公众号监督最好!!!

目光呆滞,今日不宜学习~

2、题目

首先看一下题目,

说到这里,就来说一下本题的关键,数字是在 1-n 之间的,只有一个重复数字!

同时有四个限制条件:

  1. 不能更改原数组(假设数组是只读的)。
  2. 只能使用额外的 O(1) 的空间。
  3. 时间复杂度小于 O(n2) 。
  4. 数组中只有一个重复的数字,但它可能不止重复出现一次。

要注意第一个条件,所以不能排序原数组,然后再求重复的位置!!!

这里使用的方法还是二分法,不过引申出一个原理,就是——抽屉原理。

桌上有十个苹果,要把这十个苹果放到九个抽屉里,无论怎样放,我们会发现至少会有一个抽屉里面放不少于两个苹果。————百度百科

那么如何使用二分法呢?

其实也不难,思路是先拿出有效范围 [left, right] 里的中间数 mid,然后和数组中的每个元素进行比较,统计小于等于这个中间数的元素的个数 cnt。如果 cnt 大于 mid,依然根据抽屉原理,重复元素就应该在区间 [left, mid] 里,否则在区间 [mid+1, right]

为啥是 mid+1,这个前面讲过了,自己去翻一翻吧。

【手绘漫画】图解LeetCode之寻找旋转排序数组中的最小值(LeetCode153题)

【手绘漫画】图解LeetCode之寻找旋转排序数组中的最小值 II(LeetCode154题)

3、正文

首先分析一下情况,

cnt 代表小于等于猜测的元素的数量,mid 虽然是下标但是是猜测元素,这一点很重要,所以二分法的数组不再是原来的数组,而是一个新的数组了,只是没有具体的展示出来。

  • cnt > mid,说明重复数字一定在 [left, mid] 的范围内(因为小于等于 mid 的元素多,重复元素导致元素变多);
  • cnt <= mid,说明重复数字一定在 (mid, right] 的范围内(因为小于等于 mid 的元素少);

其实通过 cnt 就相当于是完成了数组的排序,把大于 mid 的放在一侧,小于等于的放在另一侧,正常情况下(没有重复元素),cnt 应该是等于 mid,但是现在出现了不等于的情况,就说明出现了重复元素,谁的元素多了,谁就有重复元素。

复杂度:

  • 时间复杂度:。(二分法的时间复杂度为 ,“加上”一个 for 循环,嵌套的复杂度是相乘的。)
  • 空间复杂度:。

4、代码

int findDuplicate(int* nums, int numsSize){
    int left,right;
    left=0;right=numsSize-1;
    while(left<right){
        int mid=left+(right-left)/2;
        int cnt=0;
        for(int i=0;i<numsSize;i++){
            if(nums[i]<=mid)
                cnt++;
        }
        if(cnt>mid){
            right=mid;
        }
        else{
            left=mid+1;
        }
    }
    return left;
}

5、讨论

这个题还有个神奇的解法,是快慢指针,不过不算是通解,以后会再给出的!!!

本文分享自微信公众号 - 程序员管小亮(PG_gxlzl2020),作者:我是管小亮

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

原始发表时间:2020-04-04

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【手绘漫画】图解LeetCode之x 的平方根(LeetCode 69题)

    可以看到,mid * mid <= x 时,所以 target 在 mid 的右侧,因为有等号,所以 left = mid,mid * mid <= x 这么写...

    我是管小亮
  • 【手绘漫画】面试必考之二分查找中回(修订版),(LeetCode 704题)

    上次讲到的更的二分查找模板在很多地方让我使用起来不是特别的舒服,感谢B站上的y大佬,让我找到了一个新的模板!!!

    我是管小亮
  • 【手绘漫画】图解LeetCode之搜索旋转排序数组(LeetCode33题),二分查找

    排序,旋转,不重复,没错,就是我,【手绘漫画】图解LeetCode之寻找旋转排序数组中的最小值(LeetCode153题)大声喊到。

    我是管小亮
  • 初创公司如何避免服务器被攻击

    大宽宽
  • Ruby 字符串 Frozen 和 unfreeze 的问题

    看超人归来的时候,记得里面有个超人叫freeze ? 这家伙有一招,喝口水,然后往外一喷 一切就 freeze 。这不 ruby 也有freeze 。

    田春峰-JCJC错别字检测
  • 大数乘法

    其实大数乘法就是在考虑大数加法的进位的同时,考虑字符串num1和字符串num2相乘时,每一位所在的位置,以及加法运算中多了一个乘法项。 可运行的cpp代码 cl...

    kalifa_lau
  • 关于决策树、这些你需要知道

    决策树是十大机器学习算法之一,可用于分类和回归问题。最初的决策树包括ID3和C4.5,后来慢慢发展到随机森林和作为梯度提升算法的基学习器模型,例如GBM算法和X...

    深度学习与Python
  • OpenCV4 + CUDA 从配置到代码.....

    首先确保你有英伟达的独立显卡(GPU),然后请到英伟达官方网站,在线检查与下载最新的显卡驱动版本。地址如下:

    小白学视觉
  • 【RPC 专栏】深入理解 RPC 之协议篇

    协议(Protocol)是个很广的概念,RPC 被称为远程过程调用协议,HTTP 和 TCP 也是大家熟悉的协议,也有人经常拿 RPC 和 RESTFUL 做对...

    芋道源码
  • OpenCV4 | 如何让传统图像处理实现三十倍加速的顶级技能

    一直有人在研习社问我,怎么去做OpenCV + CUDA的加速支持。其实网上用搜索引擎就可以找到一堆文章,但是其实你会发现,按照他们的做法基本都不会成功,原因是...

    OpenCV学堂

扫码关注云+社区

领取腾讯云代金券