287. Find the Duplicate Number

galaxy_robot 发布于2019-08-15 11:08 / 1582人阅读

摘要：如果的数字都只有一个，那么我们会形成一个闭合的环。如果有重复数字出现的话，如下这里就有一个的环，就是重复数字如果到每个数字都只出现一次，在里的个数应该就是个数大于的话，前面的数字里就会有重复。

// 如果[1,n]的数字都只有一个，那么我们会形成一个闭合的环。
idx 1 2 3 4
val 3 1 4 2
1->3->4->2 这样就是一个闭合的环。

如果有重复数字出现的话，如下：
idx 1 2 3 4 5
val 2 4 2 3 1
1->2->4->3->2->4   这里就有一个2->4->3->2的环， 2就是重复数字

public class Solution {
    public int findDuplicate(int[] nums) {
        int slow = nums[0];
        int fast = nums[nums[0]];
        
        while(slow != fast){
            slow = nums[slow];
            fast = nums[nums[fast]];
        }
        
        fast = 0;
        while(slow != fast){
            slow = nums[slow];
            fast = nums[fast];
        }
        
        return fast;
    }
}

如果1到mid每个数字都只出现一次，在nums里<=mid的个数应该就是mid.
个数大于mid的话，前面的数字里就会有重复。

public class Solution {
    public int findDuplicate(int[] nums) {
        int n = nums.length-1, lo = 1, hi = n;
        while(lo < hi){
            int mid = lo + (hi-lo)/2, count = 0;
            for(int n: nums)
                if(n <= mid) count++;
            if(count > mid) hi = mid;
            else low = mid+1;
        }
        return lo;
    }
}

idc机房托管私有云 DUPLICATE the sdp for the webrtc number

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

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

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] 287. Find the Duplicate Number

Problem 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 nu...

rickchen 2019-08-16 14:25 评论0 收藏0
287. 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,...

fevin 2019-08-14 14:26 评论0 收藏0
[Leetcode] Find the Duplicate Number 找到重复数字

摘要：暴力法复杂度时间空间思路如果不用空间的话，最直接的方法就是选择一个数，然后再遍历整个数组看是否有跟这个数相同的数就行了。二分法复杂度时间空间思路实际上，我们可以根据抽屉原理简化刚才的暴力法。 Find the Duplicate Number Given an array nums containing n + 1 integers where each integer is bet...

chnmagnus 2019-08-14 12:39 评论0 收藏0
[LeetCode] Find the Duplicate Number

Problem 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 nu...

MoAir 2019-08-15 15:53 评论0 收藏0