目标
给你一个整数数组 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] <= 10^4
- nums 由 n + 1 个 不同的 元素组成，且其中一个元素恰好重复 n 次
思路
长度为 2 * n 数组 nums 有 n + 1 个不同元素，其中恰好有一个元素重复 n 次，返回该重复元素。
除了该重复元素，其余元素各不相同。
暴力做法是使用哈希表记录元素的出现次数，如果出现次数大于 1，直接返回，空间复杂度为 O(n)。
对于本题，从下标 1 开始与第一个元素比较，如果相等直接返回。否则问题变成从 2n - 1 个元素中找重复 n 次的元素，重复元素占绝对多数，可以使用摩尔投票算法。
还可以根据重复元素的最小间隔来分析：
- 假设重复元素至少隔着一个其它元素，有
n - 1个空隙，至少有2 * n - 1个元素，可能。 - 假设重复元素至少隔着两个其它元素，有
n - 1个空隙，至少有n + 2 * (n - 1) = 3 * n - 2个元素，当n = 2时，有可能，当n > 2时，必定存在一个重复元素的间隔小于2，否则元素个数不够。
也就是说，可以检查当前元素与其前 1、2、3 个元素是否相等来找出该重复元素。空间复杂度为 O(1)。
以上算法的时间复杂度均为 O(n)，还有一种期望 O(1) 的算法，使用随机数，随机选取两个元素。它们两个相等的概率是 n/2n × (n - 1)/(2n - 1) = 1/2 * (1 - 1/n)/(2 - 1/n)，当 n = 2 时，p = 1/6，当 n -> ∞，p -> 1/4。期望循环次数 <= 6。
代码
/**
* @date 2026-01-04 14:45
*/
public class RepeatedNTimes961 {
public int repeatedNTimes_v1(int[] nums) {
int n = nums.length;
int candidate = 0;
int vote = 0;
for (int i = 1; i < n; i++) {
if (nums[i] == nums[0]) {
return nums[0];
}
if (vote == 0) {
candidate = nums[i];
vote = 1;
} else if (candidate != nums[i]) {
vote--;
} else {
return candidate;
}
}
return candidate;
}
public int repeatedNTimes(int[] nums) {
for (int i = 1; i < nums.length; i++) {
if (nums[i] == nums[i - 1] || (i >= 2 && nums[i] == nums[i - 2]) || (i >= 3 && nums[i] == nums[i - 3])) {
return nums[i];
}
}
return 0;
}
}
性能
