剑指offer - 数组中只出现一次的两个数字

数组中只出现一次的两个数字

• 题目描述
• 基础补充
• 算法思路
• 代码实现

题目描述

一个整型数组里除了两个数字只出现一次，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

示例

输入：[1,4,1,6]
返回值：[4,6]

说明：
返回的结果中较小的数排在前面

基础补充

异或（^）

异或 xor 主要用于判断两个值是否相等

0 ^ 0 = 0
1 ^ 0 = 1
0 ^ 1 = 1
1 ^ 1 = 0

同时异或满足交换性和结合性

a ^ b = b ^ a
a ^ b ^ c = a ^ (b ^ c)

简单应用

a ^ b ^ a ^ c ^ b 
= (a ^ a) ^ (b ^ b) ^ c
= 0 ^ 0 ^ c
= c

按位与（&）

运算规则

0 & 0 = 0
0 & 1 = 0
1 & 0 = 0
1 & 1 = 1

总结：两位同时为1，结果才为1，否则结果为0

应用场景
1、清零
如果想将一个单元清零，即使其全部二进制位为0，只要与一个各位都为零的数值相与，结果为零。
任何数与0做按位与都得0，比如 235 & 0 = 0
2、取一个数的指定位
比如取数 X=1010 1110 的低4位，只需要另找一个数Y，令Y的低4位为1，其余位为0，即Y=0000 1111，然后将X与Y进行按位与运算（X&Y=0000 1110）即可得到X的指定位
3、判断奇偶
只要根据最未位是0还是1来决定，为0就是偶数，为1就是奇数。因此可以用if ((a & 1) == 0) 代替 if (a % 2 == 0)来判断a是不是偶数

还有一些简单应用：
1、x & x-1 : 将二进制数据中的最后一位的1转换为0
比如 6 & （6-1），6的二进制为0110，5的二进制为0101，两数相与，得0100，将最后的1变为了0
2、x & (~x+1) ：提取出最后一位的1
比如 6 & (~6+1)，6的二进制位0110，6取反位1001，加上1为1010，两数相与得0010,提取出了最后的1

算法思路

思路一

可以使用HashMap的方法去实现，但是空间复杂度为O(n)
参考这篇文章 第一个只出现一次的字符

思路二

思路一并不是一个最佳的解决办法，最佳的解决办法应该是位运算。

我们知道了两个相同的数字做异或运算等于0（2^2=0）
因此我们可以遍历数组，将数组中的数字一起做异或，则相同的数字会约简掉,最后会得到不相同的数字，比如 1 ^ 4 ^ 1 ^ 6 = 4 ^ 6 = 0100 ^ 0110 = 0010

但是最后得出的结果并不能很好地分开。比如得到的0010并不能很好地拆分出 0100和0110

此时可以做一个 x & (~x+1) 的算法，提取出最后面的1。拿 xor = 4 ^ 6来说,
那么 rightone = xor & (~xor+1) = 0010，提取出最后的1

然后再一次遍历数组，凡是和 rightone 相与 &不等于0的，都再次加入异或运算，等于0的不加入，这样可以排除掉其中一个只出现一次的字符

代码实现

实现一

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param array int整型一维数组
     * @return int整型一维数组
     */
    public int[] FindNumsAppearOnce (int[] array) {
        // write code here
        int[] res = new int[2];
        int index = 0;
        HashMap<Integer,Boolean> map = new HashMap<>();
        for (int i : array) {
            map.put(i,!map.containsKey(i));
        }
        for(int i:array){
            if (map.get(i)) {
                res[index++] = i;
                if(index==2){
                    break;
                }
            }
        }
        Arrays.sort(res);
        return res;
    }
}

实现二

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param array int整型一维数组
     * @return int整型一维数组
     */
    public int[] FindNumsAppearOnce (int[] array) {
        // write code here
        //array = [1,4,1,6]
        int xor = 0;
        for (int num : array) {
            xor ^= num;
        }
        //此时xor = 4^6
        int rightone = xor & (~xor+1);//提取出最右边的1,即0010
        int onlyone = 0;//用来保存只出现1次的数字的其中一个
        for (int num : array) {
            if ((rightone & num) != 0) {
                onlyone ^= num;
            }
        }
        //此时onlyone = 6
        int otherone = onlyone^xor;//再次做异或运算可以得出另一个，4^6^6=4
        if(onlyone>=otherone){
            return new int[]{otherone, onlyone};
        }else{
            return new int[]{onlyone, otherone};
        }
    }
}