README.md

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

难度：简单

https://leetcode.cn/problems/n-repeated-element-in-size-2n-array/

题目

给你一个整数数组 nums，该数组具有以下属性：

• nums.length == 2 * n.
• nums 包含 n + 1 个 不同的 元素
• nums 中恰有一个元素重复 n 次

找出并返回重复了 n 次的那个元素。

示例

示例 1：

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

示例 2：

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

示例 3：

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

解题

哈希表

/**
 * 哈希表
 * @desc 时间复杂度 O(N)  空间复杂度 O(N)
 * @param nums
 * @returns
 */
export function repeatedNTimes(nums: number[]): number {
  const n = nums.length / 2
  const counts = new Map<number, number>()

  for (let i = 0; i < nums.length; i++)
    counts.set(nums[i], counts.has(nums[i]) ? counts.get(nums[i])! + 1 : 1)

  for (const [num, count] of counts.entries())
    if (count === n) return num

  return -1
}

数学

/**
 * 数学
 * @desc 时间复杂度 O(N)  空间复杂度 O(1)
 * @param nums
 * @returns
 */
export function repeatedNTimes2(nums: number[]): number {
  const len = nums.length

  // 重复元素 x 相邻之间至少都隔 2 个位置
  for (let gap = 1; gap <= 3; gap++) {
    for (let i = 0; i + gap < len; i++) {
      if (nums[i] === nums[i + gap])
        return nums[i]
    }
  }

  return -1
}