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

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

问题描述

给定一个整数数组nums，其长度为2N。数组中恰好有一个元素重复了N次，其余N个元素都是唯一的。请返回重复了N次的元素。

约束条件：

• 2 <= nums.length <= 10000
• nums.length是偶数
• 0 <= nums[i] < 10000
• 数组中恰好有一个元素重复了N次

示例：

输入: [1,2,3,3] 输出: 3 解释: 数组长度为4 (2N=4, N=2)，元素3重复了2次。 输入: [2,1,2,5,3,2] 输出: 2 解释: 数组长度为6 (2N=6, N=3)，元素2重复了3次。 输入: [5,1,5,2,5,3,5,4] 输出: 5 解释: 数组长度为8 (2N=8, N=4)，元素5重复了4次。

算法思路

方法一：哈希表计数

使用哈希表统计每个元素的出现次数，找到出现次数为N的元素。

方法二：数学

由于数组长度为2N，有一个元素出现N次，其余N个元素各出现 1 次。重复元素占据了数组的一半。

代码实现

方法一：哈希表计数

importjava.util.*;classSolution{/** * 使用哈希表统计元素频次，找到重复N次的元素 * * @param nums 长度为2N的整数数组 * @return 重复了N次的元素 */publicintrepeatedNTimes(int[]nums){Map<Integer,Integer>count=newHashMap<>();intn=nums.length/2;// 重复次数for(intnum:nums){count.put(num,count.getOrDefault(num,0)+1);// 一旦发现某个元素出现次数达到n，立即返回if(count.get(num)==n){returnnum;}}return-1;}}

方法二：间隔

classSolution{/** * 重复元素间隔不超过2 * * @param nums 长度为2N的整数数组 * @return 重复了N次的元素 */publicintrepeatedNTimes(int[]nums){// 检查所有间隔为1的相邻元素对for(inti=0;i<nums.length-1;i++){if(nums[i]==nums[i+1]){returnnums[i];}}// 检查所有间隔为2的元素对for(inti=0;i<nums.length-2;i++){if(nums[i]==nums[i+2]){returnnums[i];}}// 检查所有间隔为3的元素对（只在小数组中需要）for(inti=0;i<nums.length-3;i++){if(nums[i]==nums[i+3]){returnnums[i];}}// 对于长度为4的特殊情况，检查首尾元素returnnums[0];}}

算法分析

方法一：哈希表计数

• 时间复杂度：O(N)
  • 最坏情况下需要遍历整个数组
  • 平均情况下可能提前找到答案
• 空间复杂度：O(N)
  • 哈希表最多存储 N+1 个不同元素

方法二：间隔

• 时间复杂度：O(N)
  • 只需要三次线性扫描
• 空间复杂度：O(1)
  • 只使用常数额外空间

算法过程

输入[5,1,5,2,5,3,5,4]（N=4）：

方法一：

1. 统计频次：5→1, 1→1, 5→2, 2→1, 5→3, 3→1, 5→4
2. 当 5 的计数达到 4 时，立即返回 5

方法二：

1. 检查相邻元素：5≠1, 1≠5, 5≠2, 2≠5, 5≠3, 3≠5, 5≠4 → 无匹配
2. 检查间隔为2的元素：5==5（索引0和2）→ 返回 5

测试用例

publicclassTestRepeatedNTimes{publicstaticvoidmain(String[]args){Solutionsolution=newSolution();// 测试用例1：基本示例int[]nums1={1,2,3,3};System.out.println("Test 1: "+solution.repeatedNTimes(nums1));// 3// 测试用例2：N=3的情况int[]nums2={2,1,2,5,3,2};System.out.println("Test 2: "+solution.repeatedNTimes(nums2));// 2// 测试用例3：N=4的情况int[]nums3={5,1,5,2,5,3,5,4};System.out.println("Test 3: "+solution.repeatedNTimes(nums3));// 5// 测试用例4：相邻重复int[]nums4={1,1,2,3};System.out.println("Test 4: "+solution.repeatedNTimes(nums4));// 1// 测试用例5：间隔为2的重复int[]nums5={1,2,1,3};System.out.println("Test 5: "+solution.repeatedNTimes(nums5));// 1// 测试用例6：最大规模int[]nums6=newint[10000];for(inti=0;i<5000;i++){nums6[i]=9999;// 重复5000次}for(inti=5000;i<10000;i++){nums6[i]=i-5000;// 其他唯一元素}System.out.println("Test 6: "+solution.repeatedNTimes(nums6));// 9999}}

关键点

1. 问题：

   • 重复元素占数组一半

2. 间隔：

   • 重复元素无法完全均匀分散
   • 必然存在两个重复元素的距离不超过 2

常见问题

1. 为什么方法二中只需要检查间隔1、2、3？
   • 通过鸽巢原理可以证明，在 2N 长度的数组中放置 N 个相同元素，必然存在两个相同元素的距离 ≤ 3。
   • 对于 N≥3，距离 ≤ 2 就足够了。