原文链接: https://leetcode-cn.com/problems/n-repeated-element-in-size-2n-array

英文原文

You are given an integer array nums with the following properties:

• nums.length == 2 * n.
• nums contains n + 1 unique elements.
• Exactly one element of nums is repeated n times.

Return the element that is repeated n times.

 

Example 1:

Input: nums = [1,2,3,3]
Output: 3

Example 2:

Input: nums = [2,1,2,5,3,2]
Output: 2

Example 3:

Input: nums = [5,1,5,2,5,3,5,4]
Output: 5

 

Constraints:

• 2 <= n <= 5000
• nums.length == 2 * n
• 0 <= nums[i] <= 104
• nums contains n + 1 unique elements and one of them is repeated exactly n times.

中文题目

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

通过代码

官方题解

方法 1：计数

想法和算法

直接计数元素的个数。利用 HashMap 或者数组，这里使用 HashMap。

然后，元素数量超过 1 的就是答案。

[]
class Solution {
    public int repeatedNTimes(int[] A) {
        Map<Integer, Integer> count = new HashMap();
        for (int x: A) {
            count.put(x, count.getOrDefault(x, 0) + 1);
        }

        for (int k: count.keySet())
            if (count.get(k) > 1)
                return k;

        throw null;
    }
}

[]
class Solution(object):
    def repeatedNTimes(self, A):
        count = collections.Counter(A)
        for k in count:
            if count[k] > 1:
                return k

复杂度分析

• 时间复杂度：$O(N)$，其中 $N$ 是 A 的长度。
• 空间复杂度：$O(N)$。

方法 2：比较

想法和算法

一旦找到一个重复元素，那么一定就是答案。我们称这个答案为主要元素。

考虑所有长度为 4 的子序列，在子序列中一定至少含有两个主要元素。

这是因为：

• 长度为 2 的子序列中都是主要元素，或者；
• 每个长度为 2 的子序列都恰好含有 1 个主要元素，这意味着长度为 4 的子序列一定含有 2 个主要元素。

因此，只需要比较所有距离为 1，2 或者 3 的邻居元素即可。

[]
class Solution {
    public int repeatedNTimes(int[] A) {
        for (int k = 1; k <= 3; ++k)
            for (int i = 0; i < A.length - k; ++i)
                if (A[i] == A[i+k])
                    return A[i];

        throw null;
    }
}

[]
class Solution(object):
    def repeatedNTimes(self, A):
        for k in xrange(1, 4):
            for i in xrange(len(A) - k):
                if A[i] == A[i+k]:
                    return A[i]

复杂度分析

• 时间复杂度：$O(N)$，其中 $N$ 是 A 的长度。
• 空间复杂度：$O(1)$。

统计信息

通过次数	提交次数	AC比率
37897	55993	67.7%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言