简单

问题描述

给你一个整数数组 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

提示：

• 2 <= n <= 5000
• nums.length == 2 * n
• 0 <= nums[i] <= 104
• nums 由 n + 1 个 不同的 元素组成，且其中一个元素恰好重复 n 次

排序

目标值的个数有 $2n$ 个，排序后，目标值肯定会在数组中部的左边或右边，因此排序后返回数组中部的左边或右边重复的数即可。

/**
 * @param {number[]} nums
 * @return {number}
 */
var repeatedNTimes = function (nums) {
  nums.sort((a, b) => a - b)
  const mid = nums.length / 2
  if (nums[mid] === nums[mid + 1]) return nums[mid]
  return nums[mid - 1]
}

• 时间复杂度：$O(n \, log \, n)$
• 空间复杂度：$O(1)$

计数

利用哈希表进行计数，计数结果大于 $1$ 的值即为答案。

/**
 * @param {number[]} nums
 * @return {number}
 */
var repeatedNTimes = function (nums) {
  const map = new Map()
  for (const num of nums) {
    if (map.has(num)) {
      return num
    } else {
      map.set(num, 1)
    }
  }
}

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

随机

由于目标数据量为数组长度的一半，随机从数组中抽取一个数，抽到目标值的概率为 $\tfrac{1}{2}$ 。随机抽取两次，都抽到不同位置的目标值的概率约为 $\tfrac{1}{4}$ ，查找的数学期望值为 $4$，即一般情况下 $4$ 次即可找出目标值。

/**
 * @param {number[]} nums
 * @return {number}
 */
var repeatedNTimes = function (nums) {
  const n = nums.length
  while (true) {
    const idx1 = ~~(Math.random() * n)
    const idx2 = ~~(Math.random() * n)
    if (idx1 === idx2) continue
    if (nums[idx1] === nums[idx2]) return nums[idx1]
  }
}

• 时间复杂度：$O(1)$ （期望）
• 空间复杂度：$O(1)$

数学

考虑目标值在数组中的位置，相邻的目标值之间至少都隔了多少个其他数字？

显然，隔 $1$ 个数字是能够将数组构造出来的。那么，是否存在相隔 $2$ 个其他数字的呢？

若相隔 $2$ 个其他数字，那么构造出的数组长度为

$$n + 2(n - 1) = 3n - 2$$

当 $n > 2$ 时，$3n-2 > 2n$，不存在满足要求的数组。

当 $n = 2$ 时，数组的长度为 $3n-2 = 2n = 4$，能构造出满足要求的数组。

因此最多只能隔 $2$ 个其他数字。

对于每个 $nums[i]$，我们检查它之前的三个在数字（若有），如果有相等情况，说明当前的 $nums[i]$ 就是答案。

/**
 * @param {number[]} nums
 * @return {number}
 */
var repeatedNTimes = function (nums) {
  const n = nums.length
  for (let i = 0; i < n; i++) {
    if (i > 0 && nums[i] === nums[i - 1]) return nums[i]
    if (i > 1 && nums[i] === nums[i - 2]) return nums[i]
    if (i > 2 && nums[i] === nums[i - 3]) return nums[i]
  }
  return -1
}

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$