关于javascript:原地hash和时间复杂度的一点理解

话不多说间接看题目

287 寻找反复数：

给定一个蕴含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包含 1 和 n），可知至多存在一个反复的整数。假如只有一个反复的整数，找出这个反复的数。

示例

输出: [1,3,4,2,2]
输入: 2
输出: [3,1,3,4,2]
输入: 3
给你一个未排序的整数数组，请你找出其中没有呈现的最小的正整数。

先用 hash 表来解决

var fn = function(nums, target) {const map = {};
    for(let i=0; i<nums.length; ++i){if(map[nums[i]]) return nums[i]
        map[nums[i]] = 1
    }
};

很简略，完满解决，还有其余形式吗
以输出 [1,3,4,2,2] 为例，咱们最终失去的 map 是

{1:1, 2:1, 3:1, 4:1}

能够看到这个对象的 keys 是 [1,2,3,4], 就是数组下标 +1。也就是说 咱们能够把数组下标当作对象的 key，来构建这个 hashmap。从而把空间复杂度从 O(n) 降到 O(1)。

具体解题思路：循环，如果 nums[i]!== i + 1, 把 nums[i] 放到下标为 nums[i]- 1 的地位，而后把 nums[i] - 1 地位上本来的数 a，放到下标为 a - 1, 并以此循环循环，如果nums[i] === nums[nums[i] - 1] 则阐明这个数呈现了两次（被搁置到正确的地位过，或者本来就存在）。文字可能说的不分明，看代码

var findDuplicate = function(nums) {for(let i = 0, len = nums.length; i < len; ++i) {
    // 如果以后地位不是 i + 1, 进循环去换
    while(nums[i] !== i + 1) {if(nums[nums[i] - 1] === nums[i]) {return nums[i]
      }
      let temp = nums[nums[i] - 1]
      nums[nums[i] - 1] = nums[i]
      nums[i] = temp
    }
  }
};

这样咱们应用本来的数组 nums 来代替 map，使空间复杂度降成 O(1)。
须要留神的是，工夫复杂度并没有因为两层循环减少为 O(n^2)，因为指标语句（替换数值的局部）执行的次数仍然是 n，所以工夫复杂度仍然是 O(n)。
再次重申，这道题的题目要求不能批改原数组，这种解法是不符合要求的，不过因为疏忽这个条件的话比拟适合举例。上面看一道正统的原地 hash 题目。

第二题

41 缺失的第一个整数：

给你一个未排序的整数数组，请你找出其中没有呈现的最小的正整数。

示例

输出: [1,2,0]
输入: 3
输出: [3,4,-1,1]
输入: 2
输出: [7,8,9,11,12]
输入: 1

题目给的提醒是你的算法的工夫复杂度应为 O(n)，并且只能应用常数级别的额定空间。完满合乎。
要留神的是，以 [7,8,9,11,12] 为例，咱们不能为了把 7 放到数组第 (7-1) 位，而扭转数组大小，因为数组 length 是 5 那么缺失的数只有可能是 1 -6，那么大于数组 length 或者小于 0 的数就不须要管了，置为 0 就能够了。代码如下。

var firstMissingPositive = function(nums) {
  let len = nums.length
  for(let i = 0; i < len; ++i) {while(nums[i] !== i + 1 && nums[i] > 0) {if(nums[nums[i] - 1] === nums[i] || nums[i] > nums.length) {nums[i] = 0
      } else {let mid = nums[nums[i] - 1]
        nums[nums[i] - 1] = nums[i]
        nums[i] = mid
      }
    }
  }
  for(let i = 0; i < nums.length; ++i) {if(!(nums[i] > 0)) {return i + 1}
  }
  return (nums[nums.length - 1] || 0) + 1
};

第三题

80 删除排序数组中的反复项 II：

给定一个增序排列数组 nums，你须要在 原地 删除反复呈现的元素，使得每个元素最多呈现两次，返回移除后数组的新长度。
不要应用额定的数组空间，你必须在 原地 批改输出数组 并在应用 O(1) 额定空间的条件下实现。

示例

输出：nums = [1,1,1,2,2,3]
输入：5, nums = [1,1,2,2,3]
解释：函数应返回新长度 length = 5, 并且原数组的前五个元素被批改为 1, 1, 2, 2, 3。你不须要思考数组中超出新长度前面的元素。

输出：nums = [0,0,1,1,1,1,2,3,3]
输入：7, nums = [0,0,1,1,2,3,3]
解释：函数应返回新长度 length = 7, 并且原数组的前五个元素被批改为 0, 0, 1, 1, 2, 3, 3。你不须要思考数组中超出新长度前面的元素。

先说一下我一开始的思路：两个指针，一个 begin 指向第一个数，end 向后找到第一个与 begin 不同的数，如果两个指针之间间隔大于 2，阐明呈现了两次以上的雷同数字，应用 splice 删除，而后更新 begin 和 end 的地位持续。

var removeDuplicates = function(nums) {for(let begin = end = 0; begin < nums.length; ++end) {if(nums[begin] !== nums[end]) {if(end - begin > 2) {nums.splice(begin, end - begin - 2)
        begin = end = begin + 2
      } else {begin = end}
    }
  }
  return nums.length
};

我认为复杂度是 O(n), 然而疏忽了调用 splice 这个 api 自身的复杂度, 如果认为 splice 是 O(n), 那么最终复杂度应该是 O(n^2)。

而后就是原地 hash 的解法，不过这次不能单纯的用数组下标来构建了，须要借用一个指针来更新，所以还是两个指针，一个指针 begin 更新后果，一个指针 i 配合 i-1 向前推动。
如果 nums[i] !== nums[i-1] 阐明呈现了新的数字，把 double 置为 false，更新 nums[begin]
如果 nums[i] === nums[i-1] 且 double=false 阐明第一次呈现雷同的数字，更新 nums[begin]，把 double 置为 true，意为曾经有两个雷同的数字了，前面不必理：

var removeDuplicates = function(nums) {if(nums.length <= 2) return nums.length;
  var begin = 1,
    doubled = false;
  for(var i = 1; i < nums.length; i++) {if(nums[i] !== nums[i-1]) {
      doubled = false;
      nums[begin++] = nums[i];
    } else if(!doubled) {
      doubled = true;
      nums[begin++] = nums[i];
    }
  }
  nums.splice(begin);
  return begin;
};