【位运算】只出现一次的数字

一、题目描述

给你一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。

你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。

示例：

二、思路

本题是位运算的典型应用题，思路如下：

1. 我们先将所有数字进行异或运算，这样最后得到的结果就是唯二两个只出现一次的数的异或结果。

2. 拿到这个异或结果之后该如何操作，得到这两个数呢，下面的思想很巧妙：

   我们先拿到异或结果最低位的 1 所在的位置，那么我们所要的结果的两个只出现一次的数字在该位具有相反的值（一个该位是0， 一个该位是1）。我们可以根据该位是0还是1，将原数组分为两组，那么这两个只出现一次的数字一定分布在这两个不同的组中。最后我们对每组进行异或运算，得到的结果就是只出现一次的数字。

三、代码

    public int[] singleNumber(int[] nums) {
        int num = nums[0];
        for(int i=1; i<nums.length; i++){ // 得到总的异或结果
            num = num ^ nums[i];
        }
        int lowBit = 0;
        while(((num >> lowBit) & 1) != 1){ // 得到最低位 1 的位置
            lowBit++;
        }

        int num1 = 0;
        int num2 = 0;


        for(int i=0; i<nums.length; i++){ // 对两组分别异或
            if(((nums[i] >> lowBit) & 1) == 1){
                if(num1==0){
                    num1 = nums[i];
                } else {
                    num1 ^= nums[i];
                }
            } else{
                if(num2 == 0){
                    num2 = nums[i];
                } else {
                    num2 ^= nums[i];
                }
            }
        }

        int[] res = {num1, num2};

        return res;

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35