[Leetcode] Find the Duplicate Number 找到重復數字

chnmagnus 發布于2019-08-14 12:39 / 3087人閱讀

摘要：暴力法復雜度時間空間思路如果不用空間的話，最直接的方法就是選擇一個數，然后再遍歷整個數組看是否有跟這個數相同的數就行了。二分法復雜度時間空間思路實際上，我們可以根據抽屜原理簡化剛才的暴力法。

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語言

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

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