美文网首页
【剑指Offer for JS】数组中的重复数字

【剑指Offer for JS】数组中的重复数字

作者: 灵活的胖墩 | 来源:发表于2020-07-08 01:21 被阅读0次

题目描述

在一个长度为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;
}

相关文章

网友评论

      本文标题:【剑指Offer for JS】数组中的重复数字

      本文链接:https://www.haomeiwen.com/subject/zgmxcktx.html