题目描述

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

例如：如果输入长度为7的数组[2, 3, 1, 0, 2, 5, 3]，那么对应的输出是重复的数字2或者3。

解题

1. 排序后查找

function duplicateSort(numbers: number[]): number {
  const len = numbers.length;

  if (len <= 1) {
    return -1;
  }

  numbers.sort();

  for (let i = 0; i < len - 1; ++i) {
    if (numbers[i] === numbers[i + 1]) {
      return numbers[i];
    }
  }

  return -1;
}

2. 使用哈希表

从头至尾逐个扫描每个数字，若该数字不存在则将该数字加入哈希表，否则就找到了重复的数字元素。

function duplicateHashMap(numbers: number[]): number {
  const len = numbers.length;

  if (len <= 1) {
    return -1;
  }

  // 使用对象模拟HashMap
  const hashMap: { [key: string]: boolean } = {};

  for (let i = 0; i < numbers.length; ++i) {
    if (hashMap.hasOwnProperty(numbers[i])) {
      return numbers[i];
    }

    hashMap[numbers[i]] = true;
  }

  return -1;
}

这种方法还可以变为使用Set、队列等方式维护已扫描过的数字，感兴趣的可以自己尝试。

3. 交换元素位置

在题干中描述说道数组的长度为n，其包含的数字都在0~n-1的范围内。
通过分析，我们可以得知以下信息：

1. 若数组中没有重复的数字，则经过排序后，数组中第i个位置的值m与其相等，可以表示为numbers[i] = m, m = i，如果不相等，则继续扫描下一个数字；
2. 若numbers[i] === numbers[m]，则说明发现了重复的元素，返回该元素即可；
3. 若上述判断均未命中，则交换numbers[i]与numbers[m]并重复上述动作，直到所有数字扫描完毕。

function duplicate(numbers: number[]): number {
  const len = numbers.length;

  if (!len || len === 1) {
    return -1;
  }

  for (let i = 0; i < len; ++i) {
    if (numbers[i] < 0 || numbers[i] > len - 1) {
      return -1;
    }
  }

  for (let i = 0; i < len; ++i) {
    // numbers[i] = m, m = i
    while (numbers[i] !== i) {
      // numbers[i] === numbers[m]
      if (numbers[i] === numbers[numbers[i]]) {
        return numbers[i];
      }

      // 交换 numbers[i] numbers[m]
      let temp = numbers[i];
      numbers[i] = numbers[temp];
      numbers[temp] = temp;
    }
  }

  return -1;
}