刷题笔记52——数组中只出现一次的数字
题目描述
一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
思路
核心思想：一个数字异或它自己是0
- 那么，由于题目中其他的数字都出现了两次，我们可以对数组中的数字进行从左往右的异或操作
- 这样，相同的数字异或就会抵消，但最终会剩下两个只出现了一次的元素，它们做异或的结果二进制表示肯定至少含有一个1
- 于是我们想到可以将这些数字分组，怎么分呢
- 首先找到异或结果的二进制表示中右边第一个是1的位，通过数组中这一位是否为1来进行分组
- 这样，出现了两次的数肯定会在一个组中。
- 然后看数组中哪个数这一位是1，就和num1做异或；哪个数这一位不是1，就和num2做异或