企业官网建设流程全解析

直播网站排名,长沙知名网站建设,投广告哪个平台好,万户网络网站管理系统在长度 2N 的数组中找出重复 N 次的元素 问题描述 给定一个整数数组 nums#xff0c;其长度为 2N。数组中恰好有一个元素重复了 N 次#xff0c;其余 N 个元素都是唯一的。请返回重复了 N 次的元素。 约束条件#xff1a; 2 nums.length 10000nums.length 是偶数0…在长度 2N 的数组中找出重复 N 次的元素问题描述给定一个整数数组nums其长度为2N。数组中恰好有一个元素重复了N次其余N个元素都是唯一的。请返回重复了N次的元素。约束条件2 nums.length 10000nums.length是偶数0 nums[i] 10000数组中恰好有一个元素重复了N次示例输入: [1,2,3,3] 输出: 3 解释: 数组长度为4 (2N4, N2)元素3重复了2次。 输入: [2,1,2,5,3,2] 输出: 2 解释: 数组长度为6 (2N6, N3)元素2重复了3次。 输入: [5,1,5,2,5,3,5,4] 输出: 5 解释: 数组长度为8 (2N8, N4)元素5重复了4次。算法思路方法一哈希表计数使用哈希表统计每个元素的出现次数找到出现次数为N的元素。方法二数学由于数组长度为2N有一个元素出现N次其余N个元素各出现 1 次。重复元素占据了数组的一半。代码实现方法一哈希表计数importjava.util.*;classSolution{/** * 使用哈希表统计元素频次找到重复N次的元素 * * param nums 长度为2N的整数数组 * return 重复了N次的元素 */publicintrepeatedNTimes(int[]nums){MapInteger,IntegercountnewHashMap();intnnums.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(inti0;inums.length-1;i){if(nums[i]nums[i1]){returnnums[i];}}// 检查所有间隔为2的元素对for(inti0;inums.length-2;i){if(nums[i]nums[i2]){returnnums[i];}}// 检查所有间隔为3的元素对只在小数组中需要for(inti0;inums.length-3;i){if(nums[i]nums[i3]){returnnums[i];}}// 对于长度为4的特殊情况检查首尾元素returnnums[0];}}算法分析方法一哈希表计数时间复杂度O(N)最坏情况下需要遍历整个数组平均情况下可能提前找到答案空间复杂度O(N)哈希表最多存储 N1 个不同元素方法二间隔时间复杂度O(N)只需要三次线性扫描空间复杂度O(1)只使用常数额外空间算法过程输入[5,1,5,2,5,3,5,4]N4方法一统计频次5→1, 1→1, 5→2, 2→1, 5→3, 3→1, 5→4当 5 的计数达到 4 时立即返回 5方法二检查相邻元素5≠1, 1≠5, 5≠2, 2≠5, 5≠3, 3≠5, 5≠4 → 无匹配检查间隔为2的元素55索引0和2→ 返回 5测试用例publicclassTestRepeatedNTimes{publicstaticvoidmain(String[]args){SolutionsolutionnewSolution();// 测试用例1基本示例int[]nums1{1,2,3,3};System.out.println(Test 1: solution.repeatedNTimes(nums1));// 3// 测试用例2N3的情况int[]nums2{2,1,2,5,3,2};System.out.println(Test 2: solution.repeatedNTimes(nums2));// 2// 测试用例3N4的情况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[]nums6newint[10000];for(inti0;i5000;i){nums6[i]9999;// 重复5000次}for(inti5000;i10000;i){nums6[i]i-5000;// 其他唯一元素}System.out.println(Test 6: solution.repeatedNTimes(nums6));// 9999}}关键点问题重复元素占数组一半间隔重复元素无法完全均匀分散必然存在两个重复元素的距离不超过 2常见问题为什么方法二中只需要检查间隔1、2、3通过鸽巢原理可以证明在 2N 长度的数组中放置 N 个相同元素必然存在两个相同元素的距离 ≤ 3。对于 N≥3距离 ≤ 2 就足够了。