算法：找出數(shù)組中重復的數(shù)字
數(shù)組中的重復的數(shù)字
在一個長度為 n 的數(shù)組 nums 里的所有的數(shù)字都在 0～n-1 的范圍內(nèi)。數(shù)組中某些數(shù)字是重復的，但不知道有幾個數(shù)字重復了，也不知道每個數(shù)字重復了幾次。請找出數(shù)組中任意一個重復的數(shù)字。
示例
輸入：
[2, 3, 1, 0, 2, 5, 3]
輸出：
2 或 3
方法一：哈希表 / Set
由于只需要找出數(shù)組中任意一個重復的數(shù)字，因此遍歷數(shù)組，遇到重復的數(shù)字即返回。為了判斷一個數(shù)字是否重復遇到，使用集合存儲已經(jīng)遇到的數(shù)字，如果遇到的一個數(shù)字已經(jīng)在集合中，則當前的數(shù)字是重復數(shù)字。
算法流程
初始化集合為空集合，重復的數(shù)字 repeat = -1
遍歷數(shù)組中的每個元素：
將該元素加入集合中，判斷是否添加成功
如果添加失敗，說明該元素已經(jīng)在集合中，因此該元素是重復元素，將該元素的值賦給 repeat，并結束遍歷
返回 repeat
代碼
復雜度分析
時間復雜度：O(n)。遍歷數(shù)組一遍。使用哈希集合（HashSet），添加元素的時間復雜度為 O(1)，故總的時間復雜度是 O(n)。
空間復雜度：O(n)。不重復的每個元素都可能存入集合，因此占用 O(n) 額外空間。
方法二：原地交換
題目說明尚未被充分使用，即 在一個長度為 n 的數(shù)組 nums 里的所有的數(shù)字都在 0 ~ n-1 的范圍內(nèi) 。 此說明含義：數(shù)組元素的 索引 和 值 是 一對多 的關系。
因此，可遍歷數(shù)組并通過交換操作，使元素的 索引 與 值 一一對應（即 nums[i] = i）。因而，就能通過索引映射對應的值，起到與字典等價的作用。
遍歷中，第一次遇到數(shù)字 x 時，將其交換至索引 x 處；而當?shù)诙斡龅綌?shù)字 x 時，一定有 nums[x] = x ，此時即可得到一組重復數(shù)字。
算法流程
遍歷數(shù)組 nums ，設索引初始值為 i=0 :
若 nums[i] = i ： 說明此數(shù)字已在對應索引位置，無需交換，因此跳過；
若 nums[nums[i]] = nums[i]： 代表索引 nums[i] 處和索引 i 處的元素值都為 nums[i] ，即找到一組重復值，返回此值 nums[i]；
否則： 交換索引為 i 和 nums[i] 的元素值，將此數(shù)字交換至對應索引位置。
若遍歷完畢尚未返回，則返回 -1 。
代碼
復雜度分析
時間復雜度 O(N) ： 遍歷數(shù)組使用 O(N) ，每輪遍歷的判斷和交換操作使用 O(1)。
空間復雜度 O(1)： 使用常數(shù)復雜度的額外空間。
寫在最后
本文內(nèi)容出處是力扣官網(wǎng)，希望和大家一起刷算法，在后面的路上不變禿但是變強！
好兄弟可以點贊并關注我的公眾號“javaAnswer”，全部都是干貨。
