电脑网站开发者模式,移动宽带过期了怎么续费,地方门户网站源码下载,推广网站出现中性产品1、题目
给你一个整数数组 nums #xff0c;该数组具有以下属性#xff1a;
nums.length 2 * n. nums 包含 n 1 个 不同的 元素 nums 中恰有一个元素重复 n 次 找出并返回重复了 n 次的那个元素。
示例 1#xff1a;
输入#xff1a;nums [1,2,3,3] 输出#xff1a…1、题目
给你一个整数数组 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时停止遍历输出该元素。
int repeatedNTimes(vectorint nums){unordered_mapint, int cnt;int goalNumber 0;for(int num : nums){cnt[num] ;if(nums.size() /2 cnt[num]){goalNumber num;break;}}return goalNumber;}另解
记重复 n次的元素为 x。由于数组 nums 中有 n1 个不同的元素而其长度为 2n那么数组中剩余的元素均只出现了一次。也就是说我们只需要找到重复出现的元素即为答案。
因此我们可以对数组进行一次遍历并使用哈希集合存储已经出现过的元素。如果遍历到了哈希集合中的元素那么返回该元素作为答案。
class Solution {
public:int repeatedNTimes(vectorint nums) {unordered_setint found;for (int num: nums) {if (found.count(num)) {return num;}found.insert(num);}// 不可能的情况return -1;}
};
