题目

面试题56 - I. 数组中数字出现的次数

一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

示例 1：
输入：nums = [4,1,4,6]
输出：[1,6] 或 [6,1]

示例 2：
输入：nums = [1,2,10,4,1,4,3,3]
输出：[2,10] 或 [10,2]

代码

  1. class Solution {
  2.     public int[] singleNumbers(int[] nums) {
  3.         int sum=0;
  4.         for(int num:nums)
  5.         {
  6.             sum^=num;
  7.         }
  8.         //所有数互相异或，最后的结果就是两个不同的数异或之后的结果
  11.         int temp=1;
  13.         //因为异或是比较二进制，相同为0，不同为1，所以只需要找到最后一个1所在的位置
  14.         //& 两个数都为1则1，否则为0
  15.         while((sum&temp)==0){
  16.             temp<<=1; // <<=1是指 1 -> 10 ,1代表移动一位
  17.         }
  19.         int a=0;
  20.         int b=0;
  22.         //将数按照temp分为两组进行异或，根据num&temp==0的条件，那么相同的数(二进制相同)永远会被分到一起
  23.         //最后两个不同的数就会被分到两组分别异或，最后得到两个不同的数字
  24.         for(int num:nums){
  25.             if((num&temp)==0){
  26.                 a^=num;
  27.             }
  28.             else{
  29.                 b^=num;
  30.             }
  31.         }
  33.         return new int[]{a,b};
  34.     }
  35. }

拓展

位异或运算（^）

运算规则是：两个数转为二进制，然后从高位开始比较，如果相同则为0，不相同则为1。
比如：8^11.
8转为二进制是1000，11转为二进制是1011.从高位开始比较得到的是：0011.然后二进制转为十进制，就是Integer.parseInt(“0011”,2)=3;

位与运算符（&）

运算规则：两个数都转为二进制，然后从高位开始比较，如果两个数都为1则为1，否则为0。
比如：129&128.
129转换成二进制就是10000001，128转换成二进制就是10000000。从高位开始比较得到，得到10000000，即128.

解析

示例 1： 输入：nums = [4,1,4,6] 输出：[1,6] 或 [6,1]

数组 [4,1,4,6] 所以的数相互异或后得到-> 4^1^4^6 -> 1^6 -> 7 （0001）^（1110）-> 01111
那么我们如何从7得到 1和6呢

7的二进制为 01111
因为异或是通过比较二进制对应位置，相同为0，不同为1
所以我们通过位与运算符来得到这两个数二进制上第一位不同的地方
int temp=1;
//因为异或是比较二进制，相同为0，不同为1，所以只需要找到最后一个1所在的位置
//& 两个数都为1则1，否则为0
while((sum&temp)==0){
temp<<=1; // <<=1是指 1 -> 10 ,1代表移动一位
}

用该数字作为标记符来讲整个数组的数分为两个部分，条件是if((num&temp)==0)
那么相同的数因为二进制是相同的所以会被分到相同的组，然后相互异或掉，那么剩下两个不同的就会被分开
我们用a和b来接收他们就可以得到结果了