重庆互联网网站建设/网站建设需求模板

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(vector<int> &nums){unordered_map<int, 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 中有 n+1 个不同的元素，而其长度为 2n，那么数组中剩余的元素均只出现了一次。也就是说，我们只需要找到重复出现的元素即为答案。

因此我们可以对数组进行一次遍历，并使用哈希集合存储已经出现过的元素。如果遍历到了哈希集合中的元素，那么返回该元素作为答案。

class Solution {
public:int repeatedNTimes(vector<int>& nums) {unordered_set<int> found;for (int num: nums) {if (found.count(num)) {return num;}found.insert(num);}// 不可能的情况return -1;}
};