【LeetCode】136. Single Number (4 solutions)

时间:2021-12-09 15:43:10

Single Number

Given an array of integers, every element appears twice except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

解法一:用map记录每个元素的次数,返回次数为1的元素

class Solution {
public:
map<int,int> m;
int singleNumber(vector<int>& nums) {
for(int i = ; i < nums.size(); i ++)
{
if(m.find(nums[i]) == m.end())
m[nums[i]] = ;
else
m[nums[i]] = ;
} for(map<int,int>::iterator it = m.begin(); it != m.end(); it ++)
{
if(it->second == )
return it->first;
}
}
};

【LeetCode】136. Single Number (4 solutions)

解法二:利用异或操作的结合律。

同一数字x异或自己结果为0.x^x=0

任何数字x异或0结果为x.x^0=x

class Solution {
public:
int singleNumber(vector<int>& nums) {
if(nums.empty())
return ;
int ret = nums[];
for(int i = ; i < nums.size(); i ++)
ret ^= nums[i];
return ret;
}
};

【LeetCode】136. Single Number (4 solutions)

解法三:先排序,再遍历找出孤异元素

class Solution {
public:
int singleNumber(vector<int>& nums) {
sort(nums.begin(), nums.end());
//A has at least 3 elements
if(nums[] != nums[])
return nums[];
int n = nums.size();
if(nums[n-] != nums[n-])
return nums[n-];
for(int i = ; i < n-; i ++)
{
if(nums[i] != nums[i-] && nums[i] != nums[i+])
return nums[i];
}
}
};

【LeetCode】136. Single Number (4 solutions)

解法四:

位操作。不管非孤异元素重复多少次,这是通用做法。

对于右数第i位,如果孤异元素该位为0,则该位为1的元素总数为2的整数倍。

如果孤异元素该位为1,则该位为1的元素总数不为2的整数倍(也就是余1)。

换句话说,如果第i位为1的元素总数不为2的整数倍,则孤异数的第i位为1,否则为0.

(如果非孤异元素重复n次,则判断是否为n的整数倍)

class Solution {
public:
int singleNumber(vector<int>& nums) {
int count;
int result = ;
int ind = ; //mask position
int n = nums.size();
while(ind)
{
count = ;
for(int i = ; i < n; i ++)
{
if(nums[i] & ind)
count ++;
}
if(count % )
result |= ind;
ind <<= ;
}
return result;
}
};

【LeetCode】136. Single Number (4 solutions)