題目描述：找出數組中重複的數字。在一個長度為 n 的數組 nums 裡的所有數字都在 0 ～ n-1 的範圍内。數組中某些數字是重複的，但不知道有幾個數字重複了，也不知道每個數字重複了幾次。請找出數組中任意一個重複的數字。
題目描述
找出數組中重複的數字。
在一個長度為 n 的數組 nums 裡的所有數字都在 0 ～ n-1 的範圍内。數組中某些數字是重複的，但不知道有幾個數字重複了，也不知道每個數字重複了幾次。請找出數組中任意一個重複的數字。
解法 1: 使用哈希表
哈希表的結構是：number-boolean，number 就是數組中的數字，boolean 代表數字是否出現過。
整體的流程是：周遊數組中的數字，檢查是否出現過，如果出現過，那麼傳回此數字。代碼實作如下：
// ac位址：https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/
// 原文位址：https://xxoo521.com/2020-02-14-repeat-number/
/**
* @param {number[]} nums
* @return {number}
*/
var findRepeatNumber = function(nums) {
const map = {};
for (const num of nums) {
if (!map[num]) {
map[num] = true;
} else {
return num;
}
}
}; 複制
由于使用了哈希表，是以空間複雜度是 O(N)。需要周遊一次，時間複雜度是 O(1)。
解法 2: 原地哈希（推薦）
從題目描述可以知道，所有數字都在 0 ～ n-1 的範圍内。是以不需要額外開辟空間，每次周遊時，檢查目前元素是否放在了正确位置上（例如元素 i 應該放在下标為 i 的位置上）。如果放在了正确位置上，那麼繼續循環。否則：
- 下标為 num 的元素 === num，說明目前元素 num 是重複的，直接傳回
- 下标為 num 的元素 !== num，交換目前元素和下标為 num 的元素，将目前元素放入到正确位置上
代碼實作如下：
// ac位址：https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/
// 原文位址：https://xxoo521.com/2020-02-07-half-number/
/**
* @param {number[]} nums
* @return {number}
*/
var findRepeatNumber = function(nums) {
const length = nums.length;
for (let i = 0; i < length; ++i) {
//檢測下标為i的元素是否放在了位置i上
while ((num = nums[i]) !== i) {
if (num === nums[num]) {
return num;
}
[nums[i], nums[num]] = [nums[num], nums[i]];
}
}
}; 複制
這裡要注意的是，第二種情況交換完元素後，應該繼續檢測下标為 i 的元素是否放在了位置 i 上，實作上使用
while
内循環即可。以
[1, 3, 2, 3]
為例，第一次交換後，變為
[3, 1, 2, 3]
，如果沒有内循環，那麼就會跳過第一個 3，繼續周遊，而後面的元素又恰巧都在正确位置上，最終沒有檢查出重複元素。特别感謝@徹的提示。
錯誤代碼
這段代碼在 leetcode 上可以 ac，建議官方添加測試用例：
[1, 3, 2, 3]
。
// ac位址：https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/
// 原文位址：https://xxoo521.com/2020-02-14-repeat-number/
/**
* @param {number[]} nums
* @return {number}
*/
var findRepeatNumber = function(nums) {
const length = nums.length;
for (let i = 0; i < length; ++i) {
const num = nums[i];
if (num === i) {
continue;
}
if (num === nums[num]) {
return num;
} else {
[nums[i], nums[num]] = [nums[num], nums[i]];
}
}
}; 複制