961.在长度2N的数组中找出重复N次的元素

在长度 2N 的数组中找出重复 N 次的元素

给定一个整数数组 nums，长度为 2n，数组中有 n+1 个不同元素，其中 n 个元素出现恰好一次，一个元素出现 n 次。返回出现 n 次的元素。

示例 1:

输入：nums = [1,2,3,3]
输出：3

示例 2:

输入：nums = [2,1,2,5,3,2]
输出：2

提示:

• 2 <= n <= 5000
• nums.length == 2n
• 1 <= nums[i] <= 10^4

解析

由于重复元素出现 n 次，至少在前 n+1 个元素中必然包含重复元素。检查前 n+1 个元素找出重复者。

var repeatedNTimes = function (nums) {
  const n = nums.length / 2;
  const seen = new Set();

  for (const num of nums) {
    if (seen.has(num)) return num;
    seen.add(num);
    if (seen.size === n + 1) break;
  }

  return -1;
};

时间复杂度 O(N)，空间复杂度 O(N)。