LeetCode中怎么輸出數組中重復的數字

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

題目：數組中重復的數字

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

示例 1：

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

限制：2 <= n <= 100000

解法一

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

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

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

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;     } }

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

方法消耗情況

執行用時：6ms 內存消耗：48.3MB

時間復雜度

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

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

空間復雜度

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

解法二

這道題其實還有個題干不容易被發現，就是第一句：

長度為 n 的數組 nums 里的所有數字都在 0～n-1 的范圍內

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

也就是nums[i]=i。

打個比方，數組長度為5，那么里面的數字應該在0&mdash;&mdash;4。如果不存在重復數字的話，那么經過排序后數組應該為：

[0,1,2,3,4]

也就是nums[i]=i，

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

當發現一個坑有兩個蘿卜的時候，就是有重復數字的發生了。上代碼：

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;     } }

簡單說下：

遍歷數組，當發現數組下標數字不等于該下標對應位置上的數字的時候，也就是nums[i]!=i，那么我們就把nums[i]數字  放到nums[i]位置上,一直到nums[i]==i。按照一個坑位一個蘿卜，所以當你的坑位被同樣的蘿卜(數字)占到的時候，這個蘿卜就是重復的那個數字了。

假如數組為[3,1,4,2,2]

• i=0的時候，nums[i]=3。3 !=1。所以把3放到num[3]的位置，數組變成了[2,1,4,3,2]。

• 2!=0,while條件true，繼續置換，數組變成了[4,1,2,3,2]。

• 4!=0,while條件true，繼續置換，數組變成了[2,1,2,3,4]。

• 2!=0,while條件true，但是此時位置為2的坑位已經被同樣的數字占據了，所以這個2就是重復數字，return。

方法消耗情況

執行用時：0—1ms 內存消耗：46.4MB

時間復雜度

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

空間復雜度

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

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