442. 数组中重复的数据

442. 数组中重复的数据

leetcode 链接

解法一：原地交换

由于给定的 n 个数都在 [1, n] 的范围内，所以遍历数组，把对应数字放到对应位置上，最后在遍历一次数组，位置 i 上的值不是 i + 1 的，就是重复的。

/**
 * @param {number[]} nums
 * @return {number[]}
 */
function findDuplicates(nums) {
  const res = []
  let i = 0
  let tmp
  while (i < nums.length) {
    if (nums[i] !== i + 1) {
      tmp = nums[nums[i] - 1]
      if (tmp === nums[i]) {
        i++
      }
      else {
        nums[nums[i] - 1] = nums[i]
        nums[i] = tmp
      }
    }
    else {
      i++
    }
  }
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] !== i + 1) {
      res.push(nums[i])
    }
  }
  return res
}

解法二：标记法

遍历数组，假设当前值为 n，把 nums[n - 1] 的值置为负数，如果遍历过程中有另外一个值也为 n，此时 nums[n - 1] 已经为负数，则 n就是重复的，放到结果中。

/**
 * @param {number[]} nums
 * @return {number[]}
 */
function findDuplicates(nums) {
  const res = []
  for (let i = 0; i < nums.length; i++) {
    const num = Math.abs(nums[i])
    if (nums[num - 1] > 0) {
      nums[num - 1] = -nums[num - 1]
    }
    else {
      res.push(num)
    }
  }
  return res
}