LeetCode中怎么輸出數(shù)組中重復(fù)的數(shù)字，針對這個問題，這篇文章詳細介紹了相對應(yīng)的分析和解答，希望可以幫助更多想解決這個問題的小伙伴找到更簡單易行的方法。

創(chuàng)新互聯(lián)建站專業(yè)為企業(yè)提供鞍山網(wǎng)站建設(shè)、鞍山做網(wǎng)站、鞍山網(wǎng)站設(shè)計、鞍山網(wǎng)站制作等企業(yè)網(wǎng)站建設(shè)、網(wǎng)頁設(shè)計與制作、鞍山企業(yè)網(wǎng)站模板建站服務(wù)，10余年鞍山做網(wǎng)站經(jīng)驗，不只是建網(wǎng)站，更提供有價值的思路和整體網(wǎng)絡(luò)服務(wù)。

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

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

示例 1：

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

限制：2 <= n <= 100000

解法一

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

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

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

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

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

方法消耗情況

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

時間復(fù)雜度

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

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

空間復(fù)雜度

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

解法二

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

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

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

也就是nums[i]=i。

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

[0,1,2,3,4]

也就是nums[i]=i，

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

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

class Solution {     public int findRepeatNumber(int[] nums) {         int temp;         for(int i=0;i
簡單說下：
遍歷數(shù)組，當發(fā)現(xiàn)數(shù)組下標數(shù)字不等于該下標對應(yīng)位置上的數(shù)字的時候，也就是nums[i]!=i，那么我們就把nums[i]數(shù)字  放到nums[i]位置上,一直到nums[i]==i。按照一個坑位一個蘿卜，所以當你的坑位被同樣的蘿卜(數(shù)字)占到的時候，這個蘿卜就是重復(fù)的那個數(shù)字了。
假如數(shù)組為[3,1,4,2,2]
i=0的時候，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，但是此時位置為2的坑位已經(jīng)被同樣的數(shù)字占據(jù)了，所以這個2就是重復(fù)數(shù)字，return。
方法消耗情況
執(zhí)行用時：0—1ms 內(nèi)存消耗：46.4MB
時間復(fù)雜度
有一個for循環(huán)，復(fù)雜度為O(n),但是在循環(huán)中，while置換最多有可能發(fā)生n次，其實也就是一個排序的過程。但是這個while排序只會發(fā)生一次，如果發(fā)生了最大n次，那么也就代表后續(xù)不用排序了。所以復(fù)雜度就是O(n+n),也就是O(n).
空間復(fù)雜度
在空間方面，由于用的還是原數(shù)組，只是多了一個變量temp，所以空間復(fù)雜度為O(1)
關(guān)于LeetCode中怎么輸出數(shù)組中重復(fù)的數(shù)字問題的解答就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，如果你還有很多疑惑沒有解開，可以關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道了解更多相關(guān)知識。
            
            
                        

            網(wǎng)站欄目：LeetCode中怎么輸出數(shù)組中重復(fù)的數(shù)字            

            URL地址：http://weahome.cn/article/pscpjs.html