287.寻找重复数

链接：287.寻找重复数
难度：Medium
标签：位运算、数组、双指针、二分查找
简介：根据 百度百科 ，生命游戏，简称为生命，是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。

题解 1 - typescript

• 编辑时间：2020-05-26
• 执行用时：452ms
• 内存消耗：35.3MB
• 编程语言：typescript
• 解法介绍：使用 include 判断是否存在相同数即可

var findDuplicate = function (nums: number[]): number {
  for (let i = 0, len = nums.length; i < len; i++)
    if (nums.includes(nums[i], i + 1)) return nums[i];
  return 0;
};

题解 2 - typescript

• 编辑时间：2020-05-26
• 执行用时：72ms
• 内存消耗：36.8MB
• 编程语言：typescript
• 解法介绍：二分查找，通过只有一个数重复且数大小在 1~len-1 之间时进行判断

var findDuplicate = function (nums: number[]): number {
  const len = nums.length;
  let l = 1,
    r = len - 1,
    res = -1;
  while (l <= r) {
    let c = 0;
    const mid = (l + r) >> 1;
    for (const num of nums) if (num <= mid) cpp;
    if (c <= mid) {
      l = mid + 1;
    } else {
      r = mid - 1;
      res = mid;
    }
  }
  return res;
};

题解 3 - typescript

• 编辑时间：2020-05-26
• 执行用时：68ms
• 内存消耗：36.7MB
• 编程语言：typescript
• 解法介绍：利用位运算节省空间，遍历一遍即可

var findDuplicate = function (nums: number[]): number {
  const maxRadix = 30;
  let cache: number[] = new Array(2).fill(0);
  for (const num of nums) {
    const compNum = num - 1;
    const cacheNum = Math.floor(compNum / 30);
    const bit = 1 << compNum;
    if ((cache[cacheNum] & bit) !== 0) return num;
    cache[cacheNum] |= bit;
  }
  return 0;
};

题解 4 - typescript

• 编辑时间：2021-12-04
• 执行用时：100ms
• 内存消耗：47.1MB
• 编程语言：typescript
• 解法介绍：快慢指针。

function findDuplicate(nums: number[]): number {
  let p = nums[0];
  let q = nums[p];
  while (p != q) {
    p = nums[p];
    q = nums[nums[q]];
  }
  p = 0;
  while (p != q) {
    p = nums[p];
    q = nums[q];
  }
  return p;
}