• 【leetcode】寻找重复数


    一、题目描述

    给定一个包含 n + 1 个整数的数组 nums ,其数字都在 [1, n] 范围内(包括 1 和 n),可知至少存在一个重复的整数。

    假设 nums 只有 一个重复的整数 ,返回 这个重复的数 。

    你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。

    示例 1:

    输入:nums = [1,3,4,2,2]
    输出:2

    示例 2:

    输入:nums = [3,1,3,4,2]
    输出:3

    二、代码思路

    本题有三种解题方法:

    • 解法1:以时间换空间 不用hash表,直接for循环一一比对

    • 解法2:以空间换时间 用到hash表去重
      这是最常用的方法,而且实际情况中往往采用以空间换时间的策略。

    • 解法3:使用二分查找, 二分查找的解题信号往往是在给定范围内去寻找一个数,根据寻找结果再缩小寻找范围时间复杂度为ologn。

    二分查找的思路如下:

    抽屉原理:假如我们有n个抽屉,往n个抽屉里面放n + 1个数,那么必定有一个抽屉里面是重复放的。

    二分查找原理: 我们猜测一个数比如是 mid ,统计nums数组中小于等于mid的数的个数,如果发现个数大于mid,证明在 1 - mid这些数中,存在一个数在nums数组中是重复的。

    举个例子,假如1 - 3 ,mid是2,给定nums数组是 1 2 2 3,那么统计小于等于2 的数量就是3 > mid ,所以 在 1 - mid 这个区间里面存在一个数,该数在nums数组中是重复的。

    所以,我们寻找完数、判断完数、就该缩小寻找范围了,如果count > mid,那么就往1 - mid中找,反之往 mid + 1 - length 中找。

    总结一下:二分查找就是在给定范围内找出一个数,找到一个数我们就根据规则判断该数是否符合,根据符合的情况进一步缩小范围,在最后的边界值判断时候,举一个例子带入算法更容易判断边界值。

    三、代码题解
    package leetcode.lc20221205;
    
    /*
     * @author lzy
     * @version 1.0
     * @DESC 寻找一个重复数
     * */
    public class Solution01 {
        //本题有三种解法
        public int findDuplicate(int[] nums) {
            //解法1:以时间换空间 不用hash表,直接for循环一一比对
    
            //解法2:以空间换时间 用到hash表去重
    
            //解法3:使用二分查找, 二分查找的解题信号往往是在给定范围内去寻找一个数,根据寻找结果再缩小寻找范围
            //时间复杂度为ologn
            //举例子:1 2 2 3 / 1 2 3
            int length = nums.length;
            int left = 1;
            int right = length;
            while (left < right) {
                int mid = (left + right) / 2;
                int count = 0;
                for (int i = 0; i < nums.length; i++) {
                    if (nums[i] <= mid) {
                        count++;
                    }
                }
                if (count > mid) {
                    //也有可能是mid
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
            return left;
        }
    }
    
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
  • 相关阅读:
    uniapp h5文件流下载pdf文件
    当我第一次在ubuntu20.04上使用gazebo
    IT入门深似海,入门到放弃你学废了嘛
    面试问JUC(java.util.concurrent)的常见类你能答出来几句?
    elasticsearch安装 及 启动异常解决
    【libGDX】Mesh立方体贴图(6张图)
    java.net.SocketException:Connection reset
    Echarts设置饼状图保证你看的明明白白
    【ELFK】之消息队列kafka
    我变秃了,也变强了——再探博客调优
  • 原文地址:https://blog.csdn.net/weixin_44627672/article/details/128183982