LeetCode 287. 寻找重复数

简介: LeetCode 287. 寻找重复数

 287. 寻找重复数

 

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

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

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

示例 1:

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

示例 2:

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

提示:

  • 1 <= n <= 105
  • nums.length == n + 1
  • 1 <= nums[i] <= n
  • nums只有一个整数 出现 两次或多次 ,其余整数均只出现 一次


进阶:

  • 如何证明 nums 中至少存在一个重复的数字?
  • 你可以设计一个线性级时间复杂度 O(n) 的解决方案吗?


思路

二分查找法,其他方法不满足题目所给进阶要求,暂不考虑,参考 B站视频题解

每一次找中间值,考虑到1-n之间的数一定都会出现,如果非重复情况下每个数只会出现一次,故我们判断小于等于中间值元素个数如果超过了中间值则说明重复的数在左半边(正常情况下【不包含重复元素】时的对应数组的左半边),否则去右半边找(正常情况下【不包含重复元素】时的对应数组的右半边)

举例说明:

    • 正常情况下【不包含重复元素】:小于等于midVal值的个数cnt应该是与midVal值恰好相等的

      比如表示范围为[1,n=4]的nums=[1,2,3,4]中,小于等于2的元素一共有2个:1和2
    • 但在实际情况下【包含重复元素】,比如说 nums=[1,3,4,2,2],那么怎么样找出这个重复的2呢?
    • 我们可以先推理出表示范围为[1,n=4],且正常情况下【不包含重复元素】的中间值:midVal = 1 + (4-1)/2 = 2

      接着我们遍历 实际情况下【包含重复元素】的nums=[1,3,4,2,2],发现其中小于等于 midVal=2 的数实际上有3个,分别为 1,2,2,大于正常情况下的2个

      因此可以判断在实际给出的nums=[1,3,4,2,2]中,存在多余且重复的数,导致小于等于 midVal=2 的元素个数为3个(正常情况下应该为2个)


    时间复杂度:二分查找 O(nlogn)


    空间复杂度:O(1)

    // hash表,空间复杂度为O(n),不满足题目进阶要求// func findDuplicate(nums []int) int {//     m := make(map[int]int)//     for i := 0; i < len(nums); i++ {//         m[nums[i]] += 1//         if m[nums[i]] >= 2 {//             return nums[i]//         }//     }//     return -1// }// 二分法 :// 参考B站视频题解:https://www.bilibili.com/video/BV1qg41137Fg/?spm_id_from=333.337.search-card.all.click&vd_source=2c268e25ffa1022b703ae0349e3659e4// 思路:每一次找中间值,考虑到1-n之间的数一定都会出现,如果非重复情况下每个数只会出现一次,故我们判断小于等于中间值元素个数如果超过了中间值则说明重复的数在左半边,否则去右半边找/* 举例说明正常情况下【不包含重复元素】:小于等于midVal值的个数cnt应该是与midVal值恰好相等的比如表示范围为[1,n=4]的nums=[1,2,3,4]中,小于等于2的元素一共有2个:1和2但在实际情况下【包含重复元素】,比如说 nums=[1,3,4,2,2],那么怎么样找出这个重复的2呢?我们可以先推理出表示范围为[1,n=4],且正常情况下【不包含重复元素】的中间值:midVal = 1 + (4-1)/2 = 2接着我们遍历 实际情况下【包含重复元素】的nums=[1,3,4,2,2],发现其中小于等于 midVal=2 的数实际上有3个,分别为 1,2,2,大于正常情况下的2个因此可以判断在实际给出的nums=[1,3,4,2,2]中,存在多余且重复的数,导致小于等于 midVal=2 的元素个数为3个(正常情况下应该为2个)*/// 时间复杂度:二分法 O(nlogn),空间复杂度:O(1)funcfindDuplicate(nums []int) int {
    // nums的数字都在 [1, n] 范围内,所以先定位nums中元素的【值】可能出现的左右范围 low和high// 数组 nums包含n + 1 个整数,即 n + 1 = len(nums),因此 n = len(nums) - 1n :=len(nums)
    low, high :=1, n-1forlow<=high {
    midVal, cnt :=low+ (high-low) /2, 0// 统计nums中元素在区间为[1, midVal]中的个数,注意这里midVal表示的是 正常情况下【不包含重复元素】的中间值fori :=0; i<n; i++ {
    // 统计实际给出的nums中,小于等于midVal值的元素个数,正常情况下【不包含重复元素】应该是cnt刚好等于midValifnums[i] <=midVal {
    cnt++            }
            }
    // 发现cnt大于正常情况下【不包含重复元素】对应的元素个数 midVal,并且这个重复数是小于midVal的ifcnt>midVal {
    high=midVal-1// 发现cnt小于正常情况下【不包含重复元素】对应的元素个数 midVal,那就说明要找的重复数存在于大于midVal的右侧        } else {
    low=midVal+1        }
        }
    returnlow}

    image.gif


    目录
    相关文章
    |
    6月前
    【Leetcode 2645】构造有效字符串的最小插入数 —— 动态规划
    状态定义:`d[i]`为将前 i 个字符拼凑成若干个 abc 所需要的最小插入数。状态转移方程: 如果` word[i]>word[i−1]`,那么`word[i]`可以和`word[i−1]`在同一组 abc 中,`d[i]=d[i−1]−1` ;否则`word[i]`单独存在于一组 abc 中,`d[i]=d[i−1]+2`
    |
    6月前
    |
    算法 测试技术 C#
    【动态规划】LeetCode2111:使数组 K 递增的最少操作次数
    【动态规划】LeetCode2111:使数组 K 递增的最少操作次数
    |
    6月前
    leetcode-1342:将数字变成 0 的操作次数
    leetcode-1342:将数字变成 0 的操作次数
    44 0
    |
    6月前
    |
    索引
    leetcode代码记录(最长重复子数组
    leetcode代码记录(最长重复子数组
    38 0
    |
    存储 算法
    LeetCode-306 累加数
    LeetCode-306 累加数
    |
    6月前
    leetcode-287:寻找重复数
    leetcode-287:寻找重复数
    31 0
    |
    6月前
    |
    算法
    leetcode-306:累加数
    leetcode-306:累加数
    32 0
    |
    算法
    LeetCode 306.累加数
    LeetCode 306.累加数
    56 0
    |
    算法 C++ 索引
    每日算法系列【LeetCode 287】寻找重复数
    每日算法系列【LeetCode 287】寻找重复数
    109 0