LeetCode之數組中重復的數字
前言
本來今天應該繼續說Android系統方面的知識，但是我發現內容有點多，寫不完了??。
那，為了保證文章的質量，所以今天就發一篇算法題頂上了～??
算法題也是面試常考的項，之前也說過，雖然用到的比較少，但是可以從算法題中考驗一個程序員基本的邏輯思維。
今天和大家看看劍指 Offer上的一題：數組中重復的數字。
題目：數組中重復的數字
在一個長度為 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——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)
總結
以后也會偶爾來幾次算法題練習，因為我自己本身的算法題也做的不多，所以如果有說的不對地方或者需要討論的地方可以在討論群發表自己的看法。感謝大家了。
參考
https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/
