442. 数组中重复的数据

442. 数组中重复的数据

leetcode 链接

解法一：原地交换

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

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var findDuplicates = function (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[]}
 */
var findDuplicates = function (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;
};