287. Find the Duplicate Number

fevin 发布于2019-08-14 14:26 / 1838人阅读

题目：
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.

解答：
1.Binary Tree

public int findDuplicate(int[] nums) {
    int start = 1, end = nums.length - 1;
    while (start + 1 < end) {
        int mid = start + (end - start) / 2;
        int left = 0, right = 0;
        for (int a : nums) {
            if (a <= mid) left++;
        }
       
        if (left <= mid) start = mid;
        else end = mid;
    }
    int countStart = 0, countEnd = 0;
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] == start) countStart++;
        if (nums[i] == end) countEnd++;
    }
    return countStart > countEnd ? start : end;
}

2.LinkedList Find the starting point of circle

public int findDuplicate(int[] nums) {
    int n = nums.length;
    
    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 slow;
}

idc机房托管专线服务 DUPLICATE the sdp for the webrtc number

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

转载请注明本文地址：https://www.ucloud.cn/yun/65012.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

摘要：如果的数字都只有一个，那么我们会形成一个闭合的环。如果有重复数字出现的话，如下这里就有一个的环，就是重复数字如果到每个数字都只出现一次，在里的个数应该就是个数大于的话，前面的数字里就会有重复。 // 如果[1,n]的数字都只有一个，那么我们会形成一个闭合的环。 idx 1 2 3 4 val 3 1 4 2 1->3->4->2 这样就是一个闭合的环。如果有重复数字出现的话，如下：...

galaxy_robot 2019-08-15 11:08 评论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