剑指 Offer 56 - I. 数组中数字出现的次数

题目描述

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

解题思路

• a ^ b，若a == b，则为0，若a != b，则不为0。可以用异或来去除相同的数字，剩下的结果一定是两个不同数字异或的结果，表示为n。
• 由于无法从n看出是哪两个数的异或结果，所以我们必须进行分组异或。我们知道同位上的数字如果不一样，异或结果是1。所以我们可以根据这一位，将所有的数字分为两类。这样既保证了，相同的数分到了一组，两个不同的数分到不同的组。
  • 我们定义div = 1，与n进行与操作，若是0则表示该位是0，将div左移一位，如10,100……。
• 如此分为两类后，就可以将两组分别做异或操作，得到两个数字，就是结果。

class Solution {
    public int[] singleNumbers(int[] nums) {
        int n = 0;
        for (int number : nums) {
            n ^= number;
        }
        int div = 1;
        while ((div & n) == 0) {
            div <<= 1;
        }
        int a = 0;
        int b = 0;
        for (int number : nums) {
            if ((div & number) == 0) {
                a ^= number;
            } else {
                b ^= number;
            }
        }
        return new int[]{a, b};
    }
}