Hello everybody!这是我第一次写关于OJ题目的博客,因为正好学到完了C++的STL库,就顺手刷了一些OJ题。
我今天要介绍的题目虽然是力扣上的简单题,但思想很巧妙,我觉得有必要和大家分享一下!
1.题目
2.代码
class Solution {
public:
int singleNumber(vector<int>& nums) {
int val=0;
for(auto e:nums){
val^=e;//相同的数异或结果为0
}
return val;
}
};
3.提交结果
4.讲解
题目很短,相信大家可以轻松读懂,方法也有很多种,我给出了我认为的最优解。
代码虽然很短,但读懂它还是不太容易的。
核心代码是:val^=e。这行代码等价于val=val^e。
为什么val从刚开始的0逐一于nums中的数据按位异或一次就得到答案了呢?
其实这是一个累积的过程,我们要知道:
- 0和任何数异或都等于任何数。
- 而任意两个相同的数异或都等于0。
0和nums中第一个数异或得到第一个数,在接下来的累积异或的过程中,相同的数都被抵消掉了,最后剩下的那个一定是只出现了奇数次的数字。题目要求找出只出现一次的数字,一次也是奇数次,咱们的思路是符合题意的!
大家可以自己举一个例子,一试便知!