[Leetcode] Find the Duplicate Number 找到重復(fù)數(shù)字

chnmagnus 發(fā)布于2019-08-14 12:39 / 3108人閱讀

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

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.

哈希表法 復(fù)雜度

時(shí)間 O(N) 空間 O(N)

思路

遍歷數(shù)組時(shí)，用一個(gè)集合記錄已經(jīng)遍歷過(guò)的數(shù)，如果集合中已經(jīng)有了說(shuō)明是重復(fù)。但這樣要空間，不符合。

暴力法 復(fù)雜度

時(shí)間 O(N^2) 空間 O(1)

思路

如果不用空間的話，最直接的方法就是選擇一個(gè)數(shù)，然后再遍歷整個(gè)數(shù)組看是否有跟這個(gè)數(shù)相同的數(shù)就行了。

排序法 復(fù)雜度

時(shí)間 O(NlogN) 空間 O(1)

思路

更有效的方法是對(duì)數(shù)組排序，這樣遍歷時(shí)遇到前后相同的數(shù)便是重復(fù)，但這樣要修改原數(shù)組，不符合要求。

二分法 復(fù)雜度

時(shí)間 O(NlogN) 空間 O(1)

思路

實(shí)際上，我們可以根據(jù)抽屜原理簡(jiǎn)化剛才的暴力法。我們不一定要依次選擇數(shù)，然后看是否有這個(gè)數(shù)的重復(fù)數(shù)，我們可以用二分法先選取n/2，按照抽屜原理，整個(gè)數(shù)組中如果小于等于n/2的數(shù)的數(shù)量大于n/2，說(shuō)明1到n/2這個(gè)區(qū)間是肯定有重復(fù)數(shù)字的。比如6個(gè)抽屜，如果有7個(gè)襪子要放到抽屜里，那肯定有一個(gè)抽屜至少兩個(gè)襪子。這里抽屜就是1到n/2的每一個(gè)數(shù)，而襪子就是整個(gè)數(shù)組中小于等于n/2的那些數(shù)。這樣我們就能知道下次選擇的數(shù)的范圍，如果1到n/2區(qū)間內(nèi)肯定有重復(fù)數(shù)字，則下次在1到n/2范圍內(nèi)找，否則在n/2到n范圍內(nèi)找。下次找的時(shí)候，還是找一半。

注意

我們比較的mid而不是nums[mid]

因?yàn)閙id是下標(biāo)，所以判斷式應(yīng)為cnt > mid，最后返回min

代碼

public class Solution {
    public int findDuplicate(int[] nums) {
        int min = 0, max = nums.length - 1;
        while(min <= max){
            // 找到中間那個(gè)數(shù)
            int mid = min + (max - min) / 2;
            int cnt = 0;
            // 計(jì)算總數(shù)組中有多少個(gè)數(shù)小于等于中間數(shù)
            for(int i = 0; i < nums.length; i++){
                if(nums[i] <= mid){
                    cnt++;
                }
            }
            // 如果小于等于中間數(shù)的數(shù)量大于中間數(shù)，說(shuō)明前半部分必有重復(fù)
            if(cnt > mid){
                max = mid - 1;
            // 否則后半部分必有重復(fù)
            } else {
                min = mid + 1;
            }
        }
        return min;
    }
}

映射找環(huán)法 復(fù)雜度

時(shí)間 O(N) 空間 O(1)

思路

假設(shè)數(shù)組中沒(méi)有重復(fù)，那我們可以做到這么一點(diǎn)，就是將數(shù)組的下標(biāo)和1到n每一個(gè)數(shù)一對(duì)一的映射起來(lái)。比如數(shù)組是213,則映射關(guān)系為0->2, 1->1, 2->3。假設(shè)這個(gè)一對(duì)一映射關(guān)系是一個(gè)函數(shù)f(n)，其中n是下標(biāo)，f(n)是映射到的數(shù)。如果我們從下標(biāo)為0出發(fā)，根據(jù)這個(gè)函數(shù)計(jì)算出一個(gè)值，以這個(gè)值為新的下標(biāo)，再用這個(gè)函數(shù)計(jì)算，以此類推，直到下標(biāo)超界。實(shí)際上可以產(chǎn)生一個(gè)類似鏈表一樣的序列。比如在這個(gè)例子中有兩個(gè)下標(biāo)的序列，0->2->3。

但如果有重復(fù)的話，這中間就會(huì)產(chǎn)生多對(duì)一的映射，比如數(shù)組2131,則映射關(guān)系為0->2, {1，3}->1, 2->3。這樣，我們推演的序列就一定會(huì)有環(huán)路了，這里下標(biāo)的序列是0->2->3->1->1->1->1->...，而環(huán)的起點(diǎn)就是重復(fù)的數(shù)。

所以該題實(shí)際上就是找環(huán)路起點(diǎn)的題，和Linked List Cycle II一樣。我們先用快慢兩個(gè)下標(biāo)都從0開(kāi)始，快下標(biāo)每輪映射兩次，慢下標(biāo)每輪映射一次，直到兩個(gè)下標(biāo)再次相同。這時(shí)候保持慢下標(biāo)位置不變，再用一個(gè)新的下標(biāo)從0開(kāi)始，這兩個(gè)下標(biāo)都繼續(xù)每輪映射一次，當(dāng)這兩個(gè)下標(biāo)相遇時(shí)，就是環(huán)的起點(diǎn)，也就是重復(fù)的數(shù)。對(duì)這個(gè)找環(huán)起點(diǎn)算法不懂的，請(qǐng)參考Floyd"s Algorithm。

注意

第一次找快慢指針相遇用do-while循環(huán)

代碼

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;
        // 用一個(gè)新指針從頭開(kāi)始，直到和慢指針相遇
        while(find != slow){
            slow = nums[slow];
            find = nums[find];
        }
        return find;
    }
}