[Leetcode] Find the Duplicate Number 找到重复数字

chnmagnus 发布于2019-08-14 12:39 / 3039人阅读

摘要：暴力法复杂度时间空间思路如果不用空间的话，最直接的方法就是选择一个数，然后再遍历整个数组看是否有跟这个数相同的数就行了。二分法复杂度时间空间思路实际上，我们可以根据抽屉原理简化刚才的暴力法。

Find the Duplicate Number

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Note: You must not modify the array (assume the array is read only). You must use only constant, O(1) extra space. Your runtime complexity should be less than O(n2). There is only one duplicate number in the array, but it could be repeated more than once.

哈希表法 复杂度

时间 O(N) 空间 O(N)

思路

遍历数组时，用一个集合记录已经遍历过的数，如果集合中已经有了说明是重复。但这样要空间，不符合。

暴力法 复杂度

时间 O(N^2) 空间 O(1)

思路

如果不用空间的话，最直接的方法就是选择一个数，然后再遍历整个数组看是否有跟这个数相同的数就行了。

排序法 复杂度

时间 O(NlogN) 空间 O(1)

思路

更有效的方法是对数组排序，这样遍历时遇到前后相同的数便是重复，但这样要修改原数组，不符合要求。

二分法 复杂度

时间 O(NlogN) 空间 O(1)

思路

实际上，我们可以根据抽屉原理简化刚才的暴力法。我们不一定要依次选择数，然后看是否有这个数的重复数，我们可以用二分法先选取n/2，按照抽屉原理，整个数组中如果小于等于n/2的数的数量大于n/2，说明1到n/2这个区间是肯定有重复数字的。比如6个抽屉，如果有7个袜子要放到抽屉里，那肯定有一个抽屉至少两个袜子。这里抽屉就是1到n/2的每一个数，而袜子就是整个数组中小于等于n/2的那些数。这样我们就能知道下次选择的数的范围，如果1到n/2区间内肯定有重复数字，则下次在1到n/2范围内找，否则在n/2到n范围内找。下次找的时候，还是找一半。

注意

我们比较的mid而不是nums[mid]

因为mid是下标，所以判断式应为cnt > mid，最后返回min

代码

public class Solution {
    public int findDuplicate(int[] nums) {
        int min = 0, max = nums.length - 1;
        while(min <= max){
            // 找到中间那个数
            int mid = min + (max - min) / 2;
            int cnt = 0;
            // 计算总数组中有多少个数小于等于中间数
            for(int i = 0; i < nums.length; i++){
                if(nums[i] <= mid){
                    cnt++;
                }
            }
            // 如果小于等于中间数的数量大于中间数，说明前半部分必有重复
            if(cnt > mid){
                max = mid - 1;
            // 否则后半部分必有重复
            } else {
                min = mid + 1;
            }
        }
        return min;
    }
}

映射找环法 复杂度

时间 O(N) 空间 O(1)

思路

假设数组中没有重复，那我们可以做到这么一点，就是将数组的下标和1到n每一个数一对一的映射起来。比如数组是213,则映射关系为0->2, 1->1, 2->3。假设这个一对一映射关系是一个函数f(n)，其中n是下标，f(n)是映射到的数。如果我们从下标为0出发，根据这个函数计算出一个值，以这个值为新的下标，再用这个函数计算，以此类推，直到下标超界。实际上可以产生一个类似链表一样的序列。比如在这个例子中有两个下标的序列，0->2->3。

但如果有重复的话，这中间就会产生多对一的映射，比如数组2131,则映射关系为0->2, {1，3}->1, 2->3。这样，我们推演的序列就一定会有环路了，这里下标的序列是0->2->3->1->1->1->1->...，而环的起点就是重复的数。

所以该题实际上就是找环路起点的题，和Linked List Cycle II一样。我们先用快慢两个下标都从0开始，快下标每轮映射两次，慢下标每轮映射一次，直到两个下标再次相同。这时候保持慢下标位置不变，再用一个新的下标从0开始，这两个下标都继续每轮映射一次，当这两个下标相遇时，就是环的起点，也就是重复的数。对这个找环起点算法不懂的，请参考Floyd"s Algorithm。

注意

第一次找快慢指针相遇用do-while循环

代码

public class Solution {
    public int findDuplicate(int[] nums) {
        int slow = 0;
        int fast = 0;
        // 找到快慢指针相遇的地方
        do{
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while(slow != fast);
        int find = 0;
        // 用一个新指针从头开始，直到和慢指针相遇
        while(find != slow){
            slow = nums[slow];
            find = nums[find];
        }
        return find;
    }
}

云服务器 GPU云服务器 asp找到重复数据 asp找到重复数据库无重复数字寻找重复数字 c语言

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64621.html

[Leetcode] Contains Duplicate 包含重复

摘要：代码集合法复杂度时间空间思路同样使用集合，但这次我们要维护集合的大小不超过，相当于是记录一个宽度为的窗口中出现过的数字。 Contains Duplicate I Given an array of integers, find if the array contains any duplicates. Your function should return true if any v...

rozbo 2019-08-14 12:28 评论0 收藏0
前端 | 每天一个 LeetCode

摘要：在线网站地址我的微信公众号完整题目列表从年月日起，每天更新一题，顺序从易到难，目前已更新个题。这是项目地址欢迎一起交流学习。这篇文章记录我练习的 LeetCode 题目，语言 JavaScript。在线网站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公众号： showImg(htt...

张汉庆 2019-08-23 13:42 评论0 收藏0
LeetCode[287] Find the Duplicate Number

摘要：复杂度思路每次通过二分法找到一个值之后，搜索整个数组，观察小于等于这个数的个数。考虑，小于这个位置的数的个数应该是小于等于这个位置的。要做的就是像找中的环一样，考虑重复的点在哪里。考虑用快慢指针。代码把一个指针放回到开头的地方 LeetCode[287] Find the Duplicate Number Given an array nums containing n + 1 in...

canopus4u 2019-08-14 15:03 评论0 收藏0
LeetCode 攻略 - 2019 年 7 月下半月汇总（100 题攻略）

摘要：月下半旬攻略道题，目前已攻略题。目前简单难度攻略已经到题，所以后面会调整自己，在刷算法与数据结构的同时，攻略中等难度的题目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道题，目前已攻略 100 题。一目录不折腾的前端，和咸鱼有什么区别...

tain335 2019-08-26 10:28 评论0 收藏0
leetcode14 4sum

摘要：这里需要注意及时处理掉重复的情况。那么就需要尽可能排除不可能的情况来提高计算效率。因为数组已经被排序，所以可以根据数组中元素的位置判断接下来的情况是否有可能合成目标值。题目要求此处为原题地址 Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d =...

MoAir 2019-08-16 10:31 评论0 收藏0