[[375775]]

前言

本來(lái)今天應(yīng)該繼續(xù)說(shuō)Android系統(tǒng)方面的知識(shí)，但是我發(fā)現(xiàn)內(nèi)容有點(diǎn)多，寫(xiě)不完了??。

那，為了保證文章的質(zhì)量，所以今天就發(fā)一篇算法題頂上了～??

算法題也是面試常考的項(xiàng)，之前也說(shuō)過(guò)，雖然用到的比較少，但是可以從算法題中考驗(yàn)一個(gè)程序員基本的邏輯思維。

今天和大家看看劍指 Offer上的一題：數(shù)組中重復(fù)的數(shù)字。

題目：數(shù)組中重復(fù)的數(shù)字

在一個(gè)長(zhǎng)度為 n 的數(shù)組 nums 里的所有數(shù)字都在0～n-1的范圍內(nèi)。數(shù)組中某些數(shù)字是重復(fù)的，但不知道有幾個(gè)數(shù)字重復(fù)了，也不知道每個(gè)數(shù)字重復(fù)了幾次。請(qǐng)找出數(shù)組中任意一個(gè)重復(fù)的數(shù)字。

示例 1：

輸入：[2, 3, 1, 0, 2, 5, 3] 輸出：2 或 3

限制：2 <= n <= 100000

解法一

題目分析下來(lái)，主要的目的就是找到數(shù)組中的重復(fù)數(shù)字。

所以我們可以利用那些沒(méi)有重復(fù)、成員唯一的集合，比如HashSet。

HashSet的特點(diǎn)就是唯一和無(wú)序，所以只要我們把數(shù)組中的數(shù)字加到HashSet中，如果出現(xiàn)重復(fù)數(shù)字，就會(huì)加入失敗。利用這一點(diǎn)就可以完成解法。

class Solution { 
    public int findRepeatNumber(int[] nums) { 
        Set<Integer> set = new HashSet<Integer>(); 
        int repeat = -1; 
        for (int num : nums) { 
            if (!set.add(num)) { 
                repeat = num; 
                break; 
            } 
        } 
        return repeat; 
    } 
} 

代碼還是比較簡(jiǎn)單的吧，設(shè)置一個(gè)空的HashSet集合，然后依次add數(shù)字進(jìn)去，出現(xiàn)失敗的情況(也就是add方法返回false)，也就代表數(shù)字出現(xiàn)了重復(fù)。

方法消耗情況

執(zhí)行用時(shí)：6ms 
內(nèi)存消耗：48.3MB 

時(shí)間復(fù)雜度

由于用到了一個(gè)for單循環(huán),復(fù)雜度為O(n)，其他的代碼復(fù)雜度都為O(1),包括set.add的復(fù)雜度也是O(1)。

所以總的時(shí)間復(fù)雜度為O(n)。

空間復(fù)雜度

如果set集合add一次就會(huì)占用一次空間，所以n次循環(huán)，最壞情況空間復(fù)雜度就為O(n)

解法二

這道題其實(shí)還有個(gè)題干不容易被發(fā)現(xiàn)，就是第一句：

長(zhǎng)度為 n 的數(shù)組 nums 里的所有數(shù)字都在 0～n-1 的范圍內(nèi)

這句話(huà)的意思就是，如果沒(méi)有重復(fù)數(shù)字的情況下，這個(gè)數(shù)組在排序后應(yīng)該是數(shù)組中下標(biāo)為i的位置所在的值應(yīng)該是等于i的。

也就是nums[i]=i。

打個(gè)比方，數(shù)組長(zhǎng)度為5，那么里面的數(shù)字應(yīng)該在0——4。如果不存在重復(fù)數(shù)字的話(huà)，那么經(jīng)過(guò)排序后數(shù)組應(yīng)該為：

[0,1,2,3,4] 

也就是nums[i]=i，

根據(jù)這一個(gè)特性，我們就可以依次把數(shù)字放到數(shù)字對(duì)應(yīng)的位置上，正常來(lái)說(shuō)一個(gè)數(shù)字會(huì)對(duì)應(yīng)一個(gè)數(shù)字的坑位，也就是一個(gè)蘿卜一個(gè)坑。

當(dāng)發(fā)現(xiàn)一個(gè)坑有兩個(gè)蘿卜的時(shí)候，就是有重復(fù)數(shù)字的發(fā)生了。上代碼：

class Solution { 
    public int findRepeatNumber(int[] nums) { 
        int temp; 
        for(int i=0;i<nums.length;i++){ 
            while (nums[i]!=i){ 
                if(nums[i]==nums[nums[i]]){ 
                    return nums[i]; 
                } 
                temp=nums[i]; 
                nums[i]=nums[temp]; 
                nums[temp]=temp; 
            } 
        } 
        return -1; 
    } 
} 

簡(jiǎn)單說(shuō)下：

遍歷數(shù)組，當(dāng)發(fā)現(xiàn)數(shù)組下標(biāo)數(shù)字不等于該下標(biāo)對(duì)應(yīng)位置上的數(shù)字的時(shí)候，也就是nums[i]!=i，那么我們就把nums[i]數(shù)字 放到nums[i]位置上,一直到nums[i]==i。按照一個(gè)坑位一個(gè)蘿卜，所以當(dāng)你的坑位被同樣的蘿卜(數(shù)字)占到的時(shí)候，這個(gè)蘿卜就是重復(fù)的那個(gè)數(shù)字了。

假如數(shù)組為[3,1,4,2,2]

• i=0的時(shí)候，nums[i]=3。3 !=1。所以把3放到num[3]的位置，數(shù)組變成了[2,1,4,3,2]。
• 2!=0,while條件true，繼續(xù)置換，數(shù)組變成了[4,1,2,3,2]。
• 4!=0,while條件true，繼續(xù)置換，數(shù)組變成了[2,1,2,3,4]。
• 2!=0,while條件true，但是此時(shí)位置為2的坑位已經(jīng)被同樣的數(shù)字占據(jù)了，所以這個(gè)2就是重復(fù)數(shù)字，return。

方法消耗情況

執(zhí)行用時(shí)：0—1ms 
內(nèi)存消耗：46.4MB 

時(shí)間復(fù)雜度

有一個(gè)for循環(huán)，復(fù)雜度為O(n),但是在循環(huán)中，while置換最多有可能發(fā)生n次，其實(shí)也就是一個(gè)排序的過(guò)程。但是這個(gè)while排序只會(huì)發(fā)生一次，如果發(fā)生了最大n次，那么也就代表后續(xù)不用排序了。所以復(fù)雜度就是O(n+n),也就是O(n).

空間復(fù)雜度

在空間方面，由于用的還是原數(shù)組，只是多了一個(gè)變量temp，所以空間復(fù)雜度為O(1)

總結(jié)

以后也會(huì)偶爾來(lái)幾次算法題練習(xí)，因?yàn)槲易约罕旧淼乃惴}也做的不多，所以如果有說(shuō)的不對(duì)地方或者需要討論的地方可以在討論群發(fā)表自己的看法。感謝大家了。

參考

https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/