题目概述(简单难度)
题目链接：
只出现一次的数字
思路与代码
思路展现
思路1：使用set集合
使用Set来存储我们的数组中的数字，如果我们的数组中的数字在set中存在，就将Set集合中的数字删除掉，从而最终Set集合中剩下的数字就一定是只出现一次的数字.
代码示例
class Solution { public int singleNumber(int[] nums) { HashSet<Integer> set = new HashSet<>(); for(int i = 0 ; i < nums.length ; i++) { if(set.contains(nums[i])) { set.remove(nums[i]); }else { set.add(nums[i]); } } for(Integer a:set) { return a; } return 0; } }
思路2 位运算
首先先来看位运算的普及知识：
我们知道在位运算中异或运算具有交换律，也就是
A^ B ^ C=A ^ C ^ B
我们还知道一个数字和自己异或，结果是0，也就是
A^A=0；
任何数字和0异或结果还是他自己
A^0=A；
有了上面的3个公式，这题就很容易解了，假如数组的元素是
[4,1,2,1,2]
我们看到这个数组中只有1出现了一次，其他的元素都出现了2次。如果我们把数组中的所有元素全部都异或一遍,也就是下面这样
4 ^ 1 ^ 2 ^ 1 ^ 2
因为异或具有交换律，我们可以把它整理成
4 ^ (1 ^ 1) ^ (2 ^ 2)
结果就是4 ^ (1 ^ 1) ^ (2 ^ 2) = 4 ^ 0 = 4
有了这3个规律，这题就很容易解了，我们只需要把所有的数字都异或一遍，最终的结果 就是我们要求的那个数字。来看下代码
代码示例
class Solution { public int singleNumber(int[] nums) { int result = 0; for(int i = 0;i < nums.length;i++) { result ^= nums[i]; } return result; } }
关于for循环这段代码我再这里再次做一下解释:
for(int i = 0;i < nums.length;i++) { result ^= nums[i]; }
拿测试用例【4，1，2，1，2】来举例：
此时result = 0后，result ^ 4等价于 0 ^ 4 = 4,然后此时result = 4,继续往下走，不断循环遍历后变成4 ^ 1 ^ 2 ^ 1 ^ 2，此时计算机自动帮我们进行交换律，变成4 ^ (1 ^ 1) ^ (2 ^ 2) = 4 ^ 0 = 4，最后的结果4即为我们所要的结果.
