LeetCode中怎么輸出數(shù)組中重復(fù)的數(shù)字

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

題目：數(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ù)字。

所以我們可以利用那些沒有重復(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)

這句話的意思就是，如果沒有重復(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&mdash;&mdash;4。如果不存在重復(fù)數(shù)字的話，那么經(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)

關(guān)于LeetCode中怎么輸出數(shù)組中重復(fù)的數(shù)字問題的解答就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，如果你還有很多疑惑沒有解開，可以關(guān)注億速云行業(yè)資訊頻道了解更多相關(guān)知識(shí)。