jz56_1.数组中数字出现的次数

题目描述

题解

分组位运算

在做了leetcode136题后(数组中只有一个出现一次的数), 很容易想到使用异或的方法求出只出现一次的数. 但是这道题难在有两个只出现一次的数. 如果想办法将给定的数组划分成两个子数组, 并满足以下条件:

1. 两个只出现一次的数分别位于两个子数组中
2. 两个子数组中除了只出现一次的数, 其他数都在该子数组中出现了两次

只要满足了这样的条件, 那么将两个子数组各自全部异或运算, 得出的两个数字就是只出现了一次的数.

算法简述：

先将整个数组全部异或, 得出的数就是两个只出现一次的数异或结果.

找到该数二进制下的一个值为1的位, 说明两个数在这一位上是不同的.

遍历整个数组, 根据刚才选定的位值为1的分到一个子数组中, 值为0的分到一个子数组中

分别求两个子数组的异或和, 所得的两个结果就是两个只出现了一次的数

public int[] singleNumbers(int[] nums) {
    int sum = 0;
    int[] res = new int[2];
    for (int num : nums) {
        sum ^= num;
    }

    int lowBit = sum & (-sum);
    for (int num : nums) {
        if ((num & lowBit) == 0) {
            res[0] ^= num;
        }else {
            res[1] ^= num;
        }
    }
    return res;
}