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

大家好，我是 @负雪明烛。点击右上方的「+关注」↗，优质题解不间断！

题目大意

今天的题目是说，有一个长度为 的数组，其中有 种不同数字，其中有一种数字重复了 次。

让我们找出这个重复 次的数字。

解题方法

官方题解中的「哈希表」、「随机选择」方法，都很好理解。

我来解释一下「数学方法」。

这个思想就是：重复的数字之间的间隔最大为 $2$。

题目给了 ，也就是说数组的长度最少为 $4$。

我们看一下，当数组长度为 时，如果让重复的数字间隔尽可能大，我们该怎么做？

把重复的数字放在数组的两头，这样它们之间的间隔是最大的，也就是 。

当数组长度为 时，相当于在长度为 的数组后面又追加了两个数字，其中还必须有一个重复数字。

你会发现，无论是将长度为 的数组重新排列，还是追加的数字换位置，重复数字的「最小间隔」都是 。

那么，当数组长度 时，重复数字之间的「最小间隔」都是 。

综上，重复数字的「最小间隔」为 $1$ 或者 。即，下标之差的最大值为或者 。

我们从左到右遍历数组，分别比较

• $nums[i]$ 与 $nums[i + 1]$
• $nums[i]$ 与 $nums[i + 2]$
• $nums[i]$ 与 $nums[i + 3]$

一定能找到重复数字。

最坏情况是什么呢？

重复数字都集中在数组的右半部分，遍历到右边这一半的数组才能找到重复数字。

代码

代码为了简化上面

class Solution {
    public int repeatedNTimes(int[] nums) {
        int N = nums.length;
        for (int i = 0; i < nums.length - 1; ++i) {
            for (int j = 1; j <= 3 && i + j < N; ++j) {
                if (nums[i] == nums[i + j])
                    return nums[i];
            }
        }
        return -1;
    }
}

class Solution:
    def repeatedNTimes(self, nums: List[int]) -> int:
        N = len(nums)
        for i in range(N - 1):
            for j in range(1, 4):
                if nums[i] == nums[min(i + j, N - 1)]:
                    return nums[i]

class Solution {
public:
    int repeatedNTimes(vector<int>& nums) {
        const int N = nums.size();
        for (int i = 0; i < nums.size() - 1; ++i) {
            for (int j = 1; j <= 3 && i + j < N; ++j) {
                if (nums[i] == nums[i + j])
                    return nums[i];
            }
        }
        return -1;
    }
};

总结

1. 形象地理解一下，是不是更好记？
2. 注意数组下标不要越界。

我是 @负雪明烛 ，刷算法题 1000 多道，写了 1000 多篇算法题解，收获阅读量 300 万。
关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛 右侧有刷题组织，从此刷题不再孤单。

• 在刷题的时候，如果你不知道该怎么刷题，可以看 LeetCode 应该怎么刷？
• 如果你觉得题目太多，想在短时间内快速提高，可以看 LeetCode 最经典的 100 道题。
• 送你一份刷题的代码模板：【LeetCode】代码模板，刷题必会
• 我写的 1000 道 LeetCode 题解，都在这里了，免费拿走。