題目描述

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

例如：如果輸入長度為7的數(shù)組[2, 3, 1, 0, 2, 5, 3]，那么對應的輸出是重復的數(shù)字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. 使用哈希表

從頭至尾逐個掃描每個數(shù)字，若該數(shù)字不存在則將該數(shù)字加入哈希表，否則就找到了重復的數(shù)字元素。

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;
}

這種方法還可以變?yōu)槭褂肧et、隊列等方式維護已掃描過的數(shù)字，感興趣的可以自己嘗試。

3. 交換元素位置

在題干中描述說道數(shù)組的長度為n，其包含的數(shù)字都在0~n-1的范圍內。
通過分析，我們可以得知以下信息：

1. 若數(shù)組中沒有重復的數(shù)字，則經過排序后，數(shù)組中第i個位置的值m與其相等，可以表示為numbers[i] = m, m = i，如果不相等，則繼續(xù)掃描下一個數(shù)字；
2. 若numbers[i] === numbers[m]，則說明發(fā)現(xiàn)了重復的元素，返回該元素即可；
3. 若上述判斷均未命中，則交換numbers[i]與numbers[m]并重復上述動作，直到所有數(shù)字掃描完畢。

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;
}