Find Duplicates in Array

初始解法

使用 Record 记录每个数出现的次数，如果出现次数不为 1，说明有重复。

/**
 * @param {number[]} numbers
 * @return {boolean}
 */
export default function findDuplicates(numbers) {
  const records: Record<number, number> = {};
  for (const num of numbers) {
    if (num in records) {
      records[num] += 1;
    } else {
      records[num] = 1;
    }
  }
  return Object.values(records).some((value) => value !== 1);
}

使用 Set

利用 Set 的唯一性，遍历数组，如果当前数已存在 Set 中，说明是重复的。

function findDuplicates(nums: number[]): number[] {
  const seen = new Set<number>();
  const dup = [];

  for (const n of nums) {
    if (seen.has(n)) {
      dup.push(n);
    } else {
      seen.add(n);
    }
  }

  return dup;
}

时间复杂度： $O(n)$

空间复杂度： $O(n)$

排序

排序后，遍历数组，如果当前数与前一个数相等，说明是重复的。

function findDuplicates(nums: number[]) {
  nums.sort((a, b) => a - b);
  const result = [];

  for (let i = 1; i < nums.length; i++) {
    if (nums[i] === nums[i - 1]) {
      result.push(nums[i]);
    }
  }

  return result;
}

Find Duplicates in Array

初始解法

使用 Set

排序

目录