O(03).数组中重复的数字

LeetCode

注意

暴力解法

使用 map 或 set

var findRepeatNumber = function (nums) {
  var map = new map();
  for (let n of nums) {
    if (map[n]) return n;
    map[n] = true
  }
};

原地替换

• 题目描述 (长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内 ), 说明每个元素都应该与自己的下标相等，都有自己的位置

• 通过循环把每个元素放回自己的位置，如果发现被相同的元素占用，表示重复

var findRepeatNumber = function (nums) {
  var index = 0;
  while (nums[index] !== undefined) {
    var temp = nums[index];
    if (temp === index) { index += 1; continue };
    if (nums[temp] === temp) return temp;
    nums[index] = nums[temp];
    nums[temp] = temp;
  }
  return -1;
};

复杂度分析

• 时间复杂度：

• 空间复杂度：

打赏