What is the time complexity of the N-Repeated Element problem?

The time complexity is O(N), where N is the number of unique elements in the array, due to the array scan and hash lookup.

Can I solve this problem without using a hash table?

Yes, it is possible to solve the problem with other techniques like sorting or using a set, but hash tables provide the most efficient solution.

How does array scanning help in this problem?

Array scanning allows us to efficiently check for repetitions while keeping track of the count using a hash map, enabling quick identification of the repeated element.

What are the common mistakes when solving the N-Repeated Element problem?

Common mistakes include not optimizing space by tracking only the repeated element and failing to terminate the scan early once the answer is found.

What makes the N-Repeated Element problem unique?

This problem requires understanding both array scanning and hash table lookups, making it a great example of optimizing both time and space in solving problems efficiently.

#961

Easy

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

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

给你一个整数数组 nums ，该数组具有以下属性： nums.length == 2 * n . nums 包含 n + 1 个不同的元素，其中 n 个值在数组中出现恰好一次。 nums 中恰有一个元素重复 n 次找出并返回重复了 n 次的那个元素。示例 1：输入： nums = [1…

数组哈希表

题目描述

给你一个整数数组 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⁴
nums 由 n + 1 个 不同的 元素组成，且其中一个元素恰好重复 n 次

lightbulb

解题思路

方法一：哈希表

由于数组 $\textit{nums}$ 一共有 $2n$ 个元素，其中有 $n + 1$ 个不同的元素，且有一个元素重复了 $n$ 次，说明数组中的其余 $n$ 个元素都是不同的。

因此，我们只需要遍历数组 $\textit{nums}$ ，用哈希表 $s$ 记录遍历过的元素。当遍历到某个元素 $x$ 时，如果 $x$ 在哈希表 $s$ 中已经存在，说明 $x$ 是重复的元素，直接返回 $x$ 即可。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为数组 $\textit{nums}$ 的长度。

1

2

3

4

5

6

7

8

class Solution:
    def repeatedNTimes(self, nums: List[int]) -> int:
        s = set()
        for x in nums:
            if x in s:
                return x
            s.add(x)

speed

复杂度分析

指标	值
时间	O(N)
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Can the candidate explain the space-time trade-off in hash-based solutions?
question_mark
Does the candidate consider stopping the scan early upon identifying the repeated element?
question_mark
Is the candidate aware of the space complexity and its optimization?

warning

常见陷阱

外企场景

error
Using unnecessary space by tracking all elements instead of just the repeated one.
error
Failing to stop the array scan early once the repeated element is found.
error
Misunderstanding the time complexity of hash lookups and scanning.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the array is sorted? How would the solution change?
arrow_right_alt
Can we solve this problem without using a hash table? What other techniques can be applied?
arrow_right_alt
What if there are multiple repeated elements with different frequencies?

help

常见问题

外企场景

继续练习

#959 由斜杠划分区域 #963 最小面积矩形 II #957 N 天后的牢房