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

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

• 解题思路
• 代码

解题思路

由于数组中存在着两个数字不重复的情况，我们将所有的数字异或操作起来，最终得到的结果是这两个数字的异或结果：(相同的两个数字相互异或，值为0)) 最后结果一定不为0，因为有两个数字不重复。

• 但是最后得到的值是两个不相同的数异或的结果，我们要的是这两个数，那咋办呢？那就把这两个数分开，在数组中分成两个子数组
• 两个数a,b不相同，那么它们的二进制位肯定有一位不相同，而二进制位为1的地方就是两个二进制数不同的地方。（假如0101异或0010=0111，可以发现异或结果为1的地方就是两个数二进制位不同的地方）
• 为了简单，我们就从右往左，找到异或结果第一个为1的二进制位，然后从这里划分成两个数组。
• 怎么找到这个1呢?用1的二进制不断去&，比如目标数字为0010，我们最开始用0001&0010=0，证明没找到，然后左移0001为0010，再去0010(之前的0001左移过来的)&0010=1，就可以发现从右往左，第二个二进制位就是1
• 从找到的1划分。因为从这里都可把两个不同的、无重复的数字分开，其余的数字也可以从这里分开，而且其余的数字都是成对的，相同的都会分到一边去，最后就 是[a，a,b，b,c，c....X] 、[e，e,g，g,w，w,..Y]对这两个数组分别异或，得到的两个值不就是两个数组中单独的那个值嘛

代码

class Solution {
    public int[] singleNumbers(int[] nums) {
        int x = 0, y = 0, n = 0, m = 1;
        //遍历异或，最后得到的n就是两个不相同的数异或的结果
        for (int num : nums) {
            n = n ^ num;
        }

        //m=1=0001(二进制)，用m来找到二进制n中从右往左的第一个1
        while ((m & n) == 0) {
            m = m << 1;//不为1就把m左移
        }

        for (int num : nums) {              // 3. 遍历 nums 分组
            if ((num & m) != 0) {
                x ^= num;  // 4. 当 num & m != 0
            } else {
                y ^= num;                // 4. 当 num & m == 0
            }
        }
        return new int[]{x, y};          // 5. 返回出现一次的数字
    }
}