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

• 示例 1：

輸入：[2, 3, 1, 0, 2, 5, 3]
輸出：2 或 3
限制：2 <= n <= 100000

• 解題思路：

1.常規(guī)思路就是把輸入的數(shù)組排序，然后從排序的數(shù)組中找到重復(fù)的數(shù)字只需要從頭到尾掃描排序后的數(shù)組即可。排序一個長度為n的數(shù)組需要O(nlogn)的時間復(fù)雜度

2.第二種思路就是利用哈希表來解決。從頭到尾掃描數(shù)組中的數(shù)字，每掃描一個數(shù)字，就用O(1)的時間去判斷哈希表里是否包含該數(shù)字，如果哈希表里已經(jīng)存在該數(shù)字，就找到一個重復(fù)的數(shù)字，如果哈希表里面沒有這個數(shù)字，就把它加入哈希表。這個思路的時間復(fù)雜度為O(n),空間復(fù)雜度為O(n)

3.我們現(xiàn)在把數(shù)組的索引利用起來；從頭到尾掃描這個數(shù)組中的數(shù)字，當掃描到下標為i的數(shù)字時，首先比較這個數(shù)字（用m表示）是不是等于i,如果是則接著掃描下一個數(shù)字；如果不是，則拿它和第m個數(shù)字進行比較，如果它和第m個數(shù)字相等，就找到了一個重復(fù)的數(shù)字（該數(shù)字在下標為i和m的位置都出現(xiàn)了）；如果它和第m個數(shù)字不相等，就把第i個數(shù)字和第m個數(shù)字交換，把m放到屬于它的位置。接下來再重復(fù)這個比較、交換的過程，直到我們發(fā)現(xiàn)一個重復(fù)的數(shù)字

方法一：利用數(shù)組排序

/**
 * @param {number[]} nums
 * @return {number}
 */
var findRepeatNumber = function(nums) {
    var m=[];
    if (nums == null || nums.length < 0) {
        return -1;
    }
    // 題目的條件是數(shù)組 nums 里的所有數(shù)字都在 0～n-1 的范圍內(nèi)
    for (let i = 0, length = nums.length; i < length; i++) {
        if (nums[i] < 0 || nums[i] > length - 1) {
        return -1;
        }
    }
   // 排序
    nums=nums.sort();
    for(var i=0;i<nums.length-1;i++){    
        if(nums[i]==nums[i+1]) {
            return nums[i];
        }           
    }
} 
findRepeatNumber([2,3,1,0,2,5,3]);

方法二：利用哈希表

/**
 * @param {number[]} nums
 * @return {number}
 */
var findRepeatNumber = function(nums) {
    if (nums == null || nums.length < 0) {
      return -1;
    }
    // 題目的條件是數(shù)組 nums 里的所有數(shù)字都在 0～n-1 的范圍內(nèi)
    for (let i = 0, length = nums.length; i < length; i++) {
      if (nums[i] < 0 || nums[i] > length - 1) {
        return -1;
      }
    }
    // 哈希表
    let map = new Map();
    for(let i of nums){
        if(map.has(i)) return i;
        map.set(i, 1);
    }
    return null;
};
findRepeatNumber([2,3,1,0,2,5,3]);

方法三：原地交換

/**
 * @param {number[]} nums
 * @return {number}
 */
var findRepeatNumber = function(nums) {
  if (nums == null || nums.length < 0) {
    return -1;
  }
  // 題目的條件是數(shù)組 nums 里的所有數(shù)字都在 0～n-1 的范圍內(nèi)
  for (let i = 0, length = nums.length; i < length; i++) {
    if (nums[i] < 0 || nums[i] > length - 1) {
      return -1;
    }
  }
  // 思路就是把數(shù)字放到對應(yīng)的索引上  比方說數(shù)字3放到索引3的位置
  for (let i = 0; i < nums.length; i++) {
    // 如果當前數(shù)字跟對應(yīng)的索引不相同則交換
    while (nums[i] != i) {
      if (nums[i] == nums[nums[i]]) {
        return nums[i];
      }
      let temp = nums[i];
      nums[i] = nums[temp];
      nums[temp] = temp;
    }
  }
  return -1;
};
findRepeatNumber([2,3,1,0,2,5,3]);