题目描述
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
说明:
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?
样例
示例 1:
输入: [2,2,1]
输出: 1
示例 2:
输入: [4,1,2,1,2]
输出: 4
思路一
哈希集
若第一次出现,插入哈希集
第二次出现,冲哈希集内删除
最后剩下的就是那个只出现一次的数字
class Solution {
public:
int singleNumber(vector<int>& nums) {
unordered_set<int> bobo;
int ans;
for(auto i : nums){
if(bobo.count(i)) bobo.erase(i);
else bobo.insert(i);
}
for(auto j : bobo) ans = j;
return ans;
}
};
思路二
先排序,再用双指针对比。
class Solution {
public:
int singleNumber(vector<int>& nums) {
sort(nums.begin(), nums.end());
for(int i = 0, j = 1; j < nums.size(); i += 2, j += 2){
if(nums[i] != nums[j]) return nums[i];
}
return nums[nums.size() - 1];
}
};
思路三
异或
任何一个数字异或它自己都等于0。也就是说,如果我们从头到尾依次异或数组中的每一个数字,那么最终的结果刚好是那个只出现一次的数字,因为那些出现两次的数字全部在异或中抵消掉了。
class Solution {
public:
int singleNumber(vector<int>& nums) {
int ans = nums[0];
for(int i = 1; i < nums.size(); ++ i){
ans = ans ^ nums[i];
}
return ans;
}
};
思路四
map
实现效果是最差的,就不说了
class Solution {
public:
int singleNumber(vector<int>& nums) {
map<int,int> n;
int ans = 0;
for(int i = 0; i < nums.size(); ++ i){
n[nums[i]] == 1? n[nums[i]] = 2: n[nums[i]] = 1;
}
for(int j = 0; j < nums.size(); ++ j){
if(n[nums[j]] == 1) ans = nums[j];
}
return ans;
}
};