1.题目描述

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:

输入: [2,2,1]输出: 1

示例 2:

输入: [4,1,2,1,2]输出: 4

 

2.解法一：巧用“异或”操作

2.1 按位异或运算（^）

• 按位异或运算将两个运算分量的对应位按位遵照以下规则进行计算： 0 ^ 0 = 0, 0 ^ 1 = 1, 1 ^ 0 = 1, 1 ^ 1 = 0
• 即相应位的值相同的，结果为 0，不相同的结果为 1。 例如，013^035结果为026（8进制）。
• 异或运算的意思是求两个运算分量相应位值是否相异，相异的为1，相同的为0（同0异1）。
• 按位异或运算的典型用法是求一个位串信息的某几位信息的反。
• 如欲求整型变量j的最右4位信息的反，用逻辑异或运算017（8进制）^j，就能求得j最右4位的信息的反,即原来为1的位，结果是0,原来为0的位，结果是1。

       2.2 示例代码

class Solution {public:    int singleNumber(vector
     
      & nums) {        //异或运算，同0异1        for(int a : nums){            result = result ^ a;        }        return result;    }private:    int result = 0;};
     

 

参考资料：

 只出现一次的数字 [ LeetCode ]