剑指 Offer 03. 数组中重复的数字

找出数组中重复的数字。

在一个长度为 n 的数组 nums 里的所有数字都在 0 ～ n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

示例 1：

输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3

限制：

2 <= n <= 100000

解题思路

这道题实际上有三种解法：

排序（时间复杂度 O(nlogn)）
哈希表（时间复杂度 O(n)，空间复杂度 O(n)）
数组下标法

但是，数组下标法才是这道题的最优解，时间复杂度 O(n)，空间复杂度 O(1)

// 排序
 
function findRepeatNumber(nums: number[]): number {
  if (nums.length === 0) return -1;
  nums.sort((a, b) => a - b);
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] === nums[i + 1]) {
      return nums[i];
    }
  }
}

// 哈希表
 
function findRepeatNumber(nums: number[]): number {
  if (nums.length === 0) return -1;
  let hash = {};
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] in hash) {
      return nums[i];
    } else {
      hash[nums[i]] = 1;
    }
  }
}

// 数组下标法
 
function findRepeatNumber(nums: number[]): number {
  for (let i = 0; i < nums.length; i++) {
    while (i != nums[i]) {
      // 交换之前进行判断该位置是否已经存在一样的了
      // 找到重复的, 实际上重复的也就是 nums[i] nums[nums[i]]
      if (nums[i] === nums[nums[i]]) {
        return nums[i];
      }
 
      // 交换
      let temp = nums[nums[i]];
      nums[nums[i]] = nums[i];
      nums[i] = temp;
    }
  }
  // 没有找到
  return -1;
}