Easy

题目描述

给你一个整数数组 nums，具有下述性质：

  • nums.length == 2 * n
  • nums 包含 n + 1 个不同的元素，其中 n 个元素恰好出现一次
  • 恰好有一个元素在 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] <= 10^4
  • nums 包含 n + 1 个不同元素，其中一个元素恰好重复 n 次

解题思路

解题思路

这道题的关键在于理解题目条件：数组长度为 2n，包含 n+1 个不同元素，其中有一个元素重复 n 次，其他 n 个元素各出现一次。

方法一：哈希表统计 最直观的方法是使用哈希表统计每个元素的出现次数，返回出现次数大于 1 的元素。时间复杂度 O(n)，空间复杂度 O(n)。

方法二：随机采样（推荐） 由于目标元素占据了数组一半的位置，我们可以随机选择两个不同位置的元素进行比较。如果相等，说明找到了重复元素。由于重复元素占一半位置，期望尝试次数很少。

方法三：相邻元素检查 检查相邻的三个元素，如果有重复元素占据一半位置，那么在任意连续的三个位置中，必然会有重复元素相邻。我们可以检查 nums[i] == nums[i+1] 或 nums[i] == nums[i+2]。

本题解采用方法二，因为它简洁且期望性能很好。

代码实现

class Solution {
public:
    int repeatedNTimes(vector<int>& nums) {
        int n = nums.size();
        while (true) {
            int i = rand() % n;
            int j = rand() % n;
            if (i != j && nums[i] == nums[j]) {
                return nums[i];
            }
        }
    }
};

class Solution:
    def repeatedNTimes(self, nums: List[int]) -> int:
        import random
        n = len(nums)
        while True:
            i, j = random.randint(0, n-1), random.randint(0, n-1)
            if i != j and nums[i] == nums[j]:
                return nums[i]

public class Solution {
    public int RepeatedNTimes(int[] nums) {
        Random rand = new Random();
        int n = nums.Length;
        while (true) {
            int i = rand.Next(n);
            int j = rand.Next(n);
            if (i != j && nums[i] == nums[j]) {
                return nums[i];
            }
        }
    }
}

var repeatedNTimes = function(nums) {
    const n = nums.length;
    while (true) {
        const i = Math.floor(Math.random() * n);
        const j = Math.floor(Math.random() * n);
        if (i !== j && nums[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型随机采样法哈希表法
时间复杂度O(1) 期望O(n)
空间复杂度O(1)O(n)