LeetCode 刷题日记之找出数组中重复数字


对于一段程序，用不同的方法写消耗时间差距还是很大的，下面是本题的逐渐改进过程。

遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
let nums = [0, 1, 2, 3, 4, 11, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15];
let findRepeatNumber = function (nums) {
  let startIndex = 0;
  let result;
  while (startIndex < nums.length) {
    let start = nums[startIndex];
    for (let i = startIndex + 1; i < nums.length; i++) {
      if (start === nums[i]) {
        result = nums[i];
      }
    }
    startIndex++;
  }
  return result;
};

减少时间复杂度，用 set 减少遍历次数

1
2
3
4
5
6
7
8
9
10
11
12
let findRepeatNumber = function (nums) {
  let result;
  let single = new Set();
  for (let i = 0; i < nums.length; i++) {
    if (single.has(nums[i])) {
      return nums[i];
    } else {
      single.add(nums[i]);
    }
  }
  return result;
};

先排序，再使用方法二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
let findRepeatNumber = function (nums) {
  let result;
  nums = nums.sort((a, b) => {
    return a - b;
  });
  let single = new Set();
  for (let i = 0; i < nums.length; i++) {
    if (single.has(nums[i])) {
      return nums[i];
    } else {
      single.add(nums[i]);
    }
  }
  return result;
};
console.log(findRepeatNumber(nums));