287. Find the Duplicate Number

galaxy_robot 發布于2019-08-15 11:08 / 1716人閱讀

摘要：如果的數字都只有一個，那么我們會形成一個閉合的環。如果有重復數字出現的話，如下這里就有一個的環，就是重復數字如果到每個數字都只出現一次，在里的個數應該就是個數大于的話，前面的數字里就會有重復。

// 如果[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;
    }
}

GPU云服務器云服務器 DUPLICATE the sdp for the webrtc number

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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