只出现一次的数字 II C++

题目描述

给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。

示例 1：

输入：nums = [2,2,3,2] 输出：3 示例 2：

输入：nums = [0,1,0,1,0,1,99] 输出：99

提示：

1 <= nums.length <= 3 * 104 -231 <= nums[i] <= 231 - 1 nums 中，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次

进阶：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

方法一：哈希表

unordered_map的内部实现了一个哈希表，有键和值对应，键不会重复，就像字典一样，页数与内容，用来解决这道题实在是太方便了，用切片提取vector的元素，把它作为哈希表的键，出现次数作为对应的值，哈希表还会自己新增进去，都不需要判断有没有，自己就会做判断，装完哈希表之后遍历一下找出出现次数为1的就可以了。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
	unordered_map<int,int>hashmap;
	for(auto & it:nums)++hashmap[it];
	for(auto & [key,value]:hashmap)if(value==1)return key;
	return 0;
    }
};

方法二：set求和相减

首先用set把所有出现的数字存下来，这些数字只会在set里面出现一次，并计算和，然后计算所有数字的和，用set的数字和乘以3再减去所有数字的和，再除以2，剩下的数值就是只出现一次的数字了。这里需要注意数值的大小，一开始我使用的是int，样例可以过，但是提交运行的时候报运行异常，后来想到是溢出问题，看到后台数据有很大的负数，int无法表示，所以改成了long long就可以了。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
	set<int>temp;
	long long sum=0,setsum=0;
	for(auto & it:nums){
		if(temp.find(it)==temp.end())setsum+=it; 
		temp.insert(it);
		sum+=it;
	}
	return (3*setsum-sum)/2;
    }
};