题目来源:136. 只出现一次的数字 - 力扣(LeetCode)
题目:如下文
给你一个 非空 整数数组 nums
,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题,且该算法只使用常量额外空间。
答案:如下图
class Solution {
public:int singleNumber(vector<int>& nums) {int val=0;for(auto e:nums){val^=e;}return val;}
};
解析:
由题意得,每个元素均出现两次,加上一个单独出现的元素,则出现两次的元素都被异或为0,
剩下的结果就为单独出现的那个数
(1)认识异或
异或是一种二进制的位运算
两个数进行异或,在计算机底层应该是这两个数分别转换成对应的二进制数进行对应异或
,两个相同的数进行异或,则对应的二进制的数上都相同,那么二进制上的数进行异或对应
的就是0,则两个数相同的数进行异或就消失了
(2)用for循环进行遍历nums
定义val=0,用来与nums的数进行异或,将val定义为0的原因是因为0异或任何数都等于任何数,便于将出现一次的数异或到val里,使用val^=e将nums数组中的数全部异或一遍,这里我感觉要是将所有的数放在一个宏观上理解,虽然是val^=e是一个一个进行异或的,但是由于二进制进行异或累加效果等同于二进制的val去异或nums中的所有数的二进制,结果就为只出现一次的那个数
int val=0;
for(auto e:nums)
{
val^=e;
}
(3)返回val
return val