This website requires JavaScript.
en
hb

中等-数组中重复的数据

题目

给定一个整数数组 a,其中 1 ≤ a[i] ≤ n (n 为数组长度), 其中有些元素出现两次而其他元素出现一次。

找到所有出现两次的元素。

你可以不用到任何额外空间并在 O(n)时间复杂度内解决这个问题吗?

示例

输入: [4, 3, 2, 7, 8, 2, 3, 1]

输出: [2, 3]

题解

举个例子 遍历数组的次数不会少,那么我想在每次遍历的时候让当前项的值作为 index ,这个 nums[index] 为负数(*-1),对他进行判断如果为负数则就是重复的数,其中要注意题目 1 ≤ a[i] ≤ n (n为数组长度) 所以要 index-1,取值的话要用 Math.abs函数取原值

var findDuplicates = function(nums) {
  let res = []
  for (let i = 0; i < nums.length; i++) {
    let v = Math.abs(nums[i])
    if (nums[v - 1] > 0) {
      nums[v - 1] = nums[v - 1] * -1
    } else {
      res.push(v)
    }
  }
  return res
}