《剑指Offer》Java刷题 NO.40 数组中只出现一次的数字(数组、HashMap、位运算、异或)

《剑指Offer》Java刷题 NO.40 数组中只出现一次的数字(数组、HashMap、位运算、异或)

传送门：《剑指Offer刷题总目录》

时间：2020-06-24
题目：
一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

---

思路：
1.哈希法
比较简单的容易想到的就是利用HashMap来存（数字，数字出现的次数），然后遍历一遍找出出现次数为1的数字
时间复杂度O(n);空间复杂度O(n)
2.位运算
时间复杂度O(n);空间复杂度O(1)
首先：位运算中异或的性质：
n^0 = n;
n^n = 0;
n^ n ^ m = n^ (n^m) ;//异或满足结合律，结果和顺序无关
当只有一个数出现一次时，我们把数组中所有的数，依次异或运算，最后剩下的就是落单的数，因为成对儿出现的都抵消了。
依照这个思路，我们来看两个数（我们假设是AB）出现一次的数组。我们首先还是先异或，剩下的数字肯定是A、B异或的结果，这个结果的二进制中的1，表现的是A和B的不同的位。我们就取第一个1所在的位数，第一个1所在的位数可以这样来求：i=ret&(-ret),
因为计算机用补码存取二进制数，而负数的补码为反码+1，取反码：第一个1变成0，右边会变成全1，左边会和原码每一位都相反；然后+1:右边向左进位，使得原来的第一个1又重新变成1，右边变成全0，左边还是和原码每一位都相反；所以再和原码取与：只剩下第一个1所在的位还是1，其他位是全0
eg:ret=010010100
反码:101101011
-ret=101101100
假设是第3位，接着把原数组分成两组，分组标准是第3位是否为1；分组方法是用i和对应元素相与，为0就说明对应位为0，否则为1；如此，相同的数肯定在一个组，因为相同数字所有位都相同，而不同的数，肯定不在一组。然后把这两个组按照最开始的思路，分别依次异或，剩余的两个结果就是这两个只出现一次的数字。

---

import java.util.HashMap;

/**
 * @author LiMin
 * @Title: FindNumsAppearOnce
 * @Description:
 * @date 2020/6/2417:28
 */
public class FindNumsAppearOnce {
    public static void main(String[] args) {
        FindNumsAppearOnce find = new FindNumsAppearOnce();
        int[] arr = {2, 4, 3, 6, 3, 2, 5, 5};
        int[] num1 = new int[1];
        int[] num2 = new int[1];
        find.findNumsAppearOnceTwo(arr, num1, num2);
        System.out.println(num1[0] + "  " + num2[0]);
    }

    /**
     * 利用HashMap来存（数字，数字出现的次数），然后遍历一遍找出出现次数为1的数字
     */
    public void findNumsAppearOnceOne(int[] array, int num1[], int num2[]) {
        HashMap<Integer, Integer> temp = new HashMap<>();
        for (int i = 0; i < array.length; i++) {
            int number = array[i];
            if (temp.containsKey(number)) {
                int count = temp.get(number);
                temp.put(number, count + 1);
            } else temp.put(number, 1);
        }
        int j = 0;
        for (int i = 0; i < array.length; i++) {
            if (temp.get(array[i]) == 1) {
                if (j == 0) {
                    num1[j++] = array[i];
                } else if (j == 1) {
                    num2[0] = array[i];
                } else break;
            }
        }
    }

    /**
     * 位运算：利用异或 、与
     */
    public void findNumsAppearOnceTwo(int[] array, int num1[], int num2[]) {
        int ret = 0;
        for (int k : array) ret ^= k;
        int i = ret & (-ret);
        int result1 = 0;
        int result2 = 0;
        for (int k : array) {
            if ((i & k) == 0) result1 ^= k;
            else result2 ^= k;
        }
        num1[0] = result1;
        num2[0] = result2;
    }
}