算法|LeetCode题解（只出现过一次的数字）
题目描述： 在一个非空vector容器中存在一些数字，其中只有一个数字只出现过一次，其余数字都出现了两次。编写一个函数找到这个只出现过一次的数字。
要求：
不使用额外空间，并且算法应呈线性的时间复杂度。
解题核心： 按位异或运算，其中C++中按位异或运算符为^ 。
解题思路： 两数的按位异或运算即将两数转换为二进制表示后按低位对齐，高位补0，逐位比较，当某一个数的当前位为1而另一数的当前位为0时得到的当前位为1，否则为0。
此处数字1为50（二进制表示为110010）。
数字2为23（二进制表示为10111）。
【算法|LeetCode题解（只出现过一次的数字）】将其分别转换为二进制表示后低位对齐，高位补0。
逐位比对，得到运算结果37（二进制表示为100101）。
文章图片
至此，我们了解了异或运算的规则，我们可以根据百度到的一些异或运算的性质来完成本题。
性质一：
任何数与0做异或运算结果都为其本身。
性质二：
自反性，任何数与自身做异或运算结果都为0。
性质三：
异或运算满足结合律与交换律。
以上两个性质都可以有异或运算的规则轻易得到，在此不作过多说明。
故本题思路：用0依次与容器中的数做异或运算，由于以上性质，0每次与出现过两次的数做异或运算最终结果会变为0，而0与只出现过一次的数做异或运算会变为该数，故最后得到的运算结果即为只出现过一次的数。
代码实现：
C++：
int singleNumber(vector& nums)
{
int ans = 0;
for(int i = 0 ;
i < nums.size() ;
i ++)
{
ans ^= nums[i];
}
return ans;
} 本题出处：
136. 只出现一次的数字
推荐阅读
- 画解算法（1.|画解算法：1. 两数之和）
- Guava|Guava RateLimiter与限流算法
- 【Leetcode/Python】001-Two|【Leetcode/Python】001-Two Sum
- leetcode|leetcode 92. 反转链表 II
- 一个选择排序算法
- SG平滑轨迹算法的原理和实现
- ACSL|ACSL 美国计算机科学联赛 2016-2017 R4 摩天大楼-Skyscraper 题解
- 《算法》-图[有向图]
- 二叉树路径节点关键值和等于目标值（LeetCode--112&LeetCode--113）
- LeetCode算法题-11.|LeetCode算法题-11. 盛最多水的容器（Swift）