【LeetCode】只出现一次的数字系列题解

只出现一次的数字

题目链接

题目描述

给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
注意:要求是线性时间复杂度同时不使用额外的空间

样例输入

[2,2,1]

样例输出

1

解题思路

总所周知,两个一样的数进行异或操作的结果就是零。所以我们可以通过异或操作将成对的数字消掉,最后的结果便是只出现一次的数字了。

AC代码

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
int singleNumber(vector<int>& nums) {
int ans = 0;
int len = nums.size();
for (int i = 0; i < len; i++){
ans ^= nums[i];
}
return ans;
}
};

只出现一次的数字 II

题目链接

题目描述

给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现了三次。找出那个只出现了一次的元素。
注意:要求是线性时间复杂度同时不使用额外的空间

样例输入

[2,2,3,2]

样例输出

3

解题思路

参考自
根据上一题的经验,两个一样的数字可以通过异或来消除。那三个数时要怎么消除呢?我们不妨定义两个变量a和b,假设数组中数字X出现了三次
X第一次出现时

1
a = a ^ X;

X第二次出现时

1
b = b ^ X;

X第三次出现时

1
2
a = a ^ X;
b = b ^ X;

到这一步还是非常通俗易懂的。但是如何判断X是第几次出现呢?在别人的博客看到如下的公式

1
2
a = (a ^ X) & ~b;
b = (b ^ X) & ~a;

在这里除了膜拜能想到这个公式的神仙,我什么也做不了。这也太nb了。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
int singleNumber(vector<int>& nums) {
int len = nums.size();
int a = 0;
int b = 0;
for (int i = 0; i < len; i++){
a = (a ^ nums[i]) & ~b;
b = (b ^ nums[i]) & ~a;
}
return a;
}
};

只出现一次的数字 III

题目链接

题目描述

给定一个整数数组 nums,其中恰好有两个元素只出现一次,其余所有元素均出现两次。 找出只出现一次的那两个元素。

样例输入

[1,2,1,3,2,5]

样例输出

[3,5]

解题思路

与第一题一样,先将所有数字异或操作一遍,然后会得到只出现一次的那两个数字异或的结果。我们都知道异或的意义在于不同则为1,那我们可以通过这个不同位将数组重新划分为两部分,一部分为该位置为0,另外一部分为该位置为1。如何快速找到二进制表达式中最低位的1所对应的值可以通过lowbit()函数来获取

1
2
3
int lowbit(int x){
return x & -x;
}

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
int len = nums.size();
int temp = 0;
for(int i = 0; i < len; i++){
temp ^= nums[i];
}
temp = temp & (-temp);
int ans1, ans2;
ans1 = ans2 = 0;
for(int i = 0; i < len; i++){
if (nums[i] & temp)
ans1 ^= nums[i];
else
ans2 ^= nums[i];
}
vector<int> ans;
ans.push_back(ans1);
ans.push_back(ans2);
return ans;
}
};
-------------本文结束您的阅读与肯定是我持续装*的最大动力-------------