题目:剑指 Offer 56 - I. 数组中数字出现的次数
思路
解决此题首先要清楚异或的概念。相同的数异或为0，不同的数异或为1,，此外0和任何数异或等于这个数本身。
所以，本题数组里面所有数的异或=目标两个数异或。由于这两个数不同，所以异或结果必然不等于0.根据这个特性，我们可以采用分组的方法解决这个问题，且分组要满足两个条件:1.两个相同的数必须在同一组；2.两个只出现一次的数必须分配在不同组。这样我们对这两组进行异或，就可以得到两个只出现一次的数。这里拿示例1举例子:[4,1,4,6]:全部异或结果就等于1和6的异或结果。就是0001和0110异或结果是0111。0111这个二进制中1暗含什么意思?不难知道，二进制位是1，就表示1和6这个二进制位上的数不同。所以，这就是划分两个数到不同组的依据。因为0111有三个二进制位都是1，分别是第一位，第二位和第三位。这就表示了1和6的二进制数在第一、二、三位上的数是不同的。我们假设就以第一个二进制位为划分标准。当数组中的数的第一个二进制位是1的就分为第一组。数组中的数第一个二进制位是0的就划分为第二组。这样就成功的将1和6分到了不同的组别中，而相同的数例如4，因为4和4的第一个二进制位是必然相等的，这样也就实现了将两个相同的数划分到同一组。最后只需要分别将这两个组进行异或，就可以得到我们要求的答案。
解题
class Solution { public int[] singleNumbers(int[] nums) { int ret = 0; for(int num:nums){ ret ^= num;//ret最终答案就是那两个只出现一次的的数异或的结果 } //找到ret二进制数中第几位是1 int target = 1;//初始位0001 while((target & ret)==0){//如果target第一个二进制位不为1，就将target左移一位位0010，然后与相与，判断ret第二位是否为一.按此循环，知道找到ret的第一个为1的二进制位 target = target<<1; } int a = 0, b = 0; for(int num:nums){ if((num & target)==0){//第一组 a ^= num; }else{//第二组 b ^= num; } } return new int[]{a,b}; } }
