## 找出數組中重復的數字 ### 題目描述 在一個長度為 `n` 的數組里的所有數字都在 `0` 到 `n-1` 的范圍內。數組中某些數字是重復的，但不知道有幾個數字重復了，也不知道每個數字重復了幾次。請找出數組中任意一個重復的數字。例如，如果輸入長度為 `7` 的數組 `{2, 3, 1, 0, 2, 5, 3}`，那么對應的輸出是重復的數字 `2` 或者 `3`。 ### 解法 #### 解法一 排序后，順序掃描，判斷是否有重復，時間復雜度為 `O(n2)`。 #### 解法二 利用哈希表，遍歷數組，如果哈希表中沒有該元素，則存入哈希表中，否則返回重復的元素。時間復雜度為 `O(n)`，空間復雜度為 `O(n)`。 #### 解法三 長度為 `n`，元素的數值范圍也為 `n`，如果沒有重復元素，那么數組每個下標對應的值與下標相等。 從頭到尾遍歷數組，當掃描到下標 `i` 的數字 `nums[i]`： - 如果等于 `i`，繼續向下掃描； - 如果不等于 `i`，拿它與第 `nums[i]` 個數進行比較，如果相等，說明有重復值，返回 `nums[i]`。如果不相等，就把第 `i` 個數 和第 `nums[i]` 個數交換。重復這個比較交換的過程。 此算法時間復雜度為 `O(n)`，因為每個元素最多只要兩次交換，就能確定位置。空間復雜度為 `O(1)`。 ```java /** * @author bingo * @since 2018/10/27 */ public class Solution { /** * 查找數組中的重復元素 * @param numbers 數組 * @param length 數組長度 * @param duplication duplication[0]存儲重復元素 * @return boolean */ public boolean duplicate(int[] numbers, int length, int[] duplication) { if (numbers == null || length < 1) { return false; } for (int e : numbers) { if (e >= length) { return false; } } for (int i = 0; i < length; ++i) { while (numbers[i] != i) { if (numbers[i] == numbers[numbers[i]]) { duplication[0] = numbers[i]; return true; } swap(numbers, i, numbers[i]); } } return false; } private void swap(int[] numbers, int i, int j) { int t = numbers[i]; numbers[i] = numbers[j]; numbers[j] = t; } } ``` ### 測試用例 1. 長度為 n 的數組中包含一個或多個重復的數字； 2. 數組中不包含重復的數字； 3. 無效測試輸入用例（輸入空指針；長度為 n 的數組中包含 0~n-1 之外的數字）。