LeetCode.260.Single Number III 数组中只出现一次的数3

题目描述

260 Single Number III
https://leetcode-cn.com/problems/single-number-iii/

《剑指offer》面试题56 - I. 数组中数字出现的次数
https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

Example:

Input:  [1,2,1,3,2,5]
Output: [3,5]

Note:
The order of the result is not important. So in the above example, [5, 3] is also correct.
Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

---

相似题目

LeetCode.136.Single Number 数组中只出现一次的数
LeetCode.137.Single Number II 数组中只出现一次的数2
LeetCode.260.Single Number III 数组中只出现一次的数3
LeetCode.剑指offer.056.数组中数字出现的次数

---

解题过程

非常难的题，需要一个获取整数最低位1的方法 lowbit(i) = i & -i;

1、所有数异或，结果是仅出现一次的2个数a、b的异或值xor
2、lowbit(i) = i & -i; lowbit是所有数异或结果仅保留最低位1其余全是0对应的值，a、b在此位上异或结果为1说明a、b在此位的值肯定不同，那么我们就可以利用此位将a、b两数分开
3、所有数和lowbit按位与，根据在此位是1还是0分到两个子数组中，则a、b肯定分到了不同的子数组，同值的肯定也都在同一个子数组
4、则问题转变为两个 “数组中所有值都出现2次只有一个值出现1次” 的问题，子数组所有值异或可分别得到a、b值

时间复杂度 O(n)，空间复杂度 O(1)

private static class SolutionV2020 {
    public int[] singleNumber(int[] nums) {
        // 所有数异或，结果是仅出现一次的2个数a、b的异或值
        int xor = 0;
        for (int n : nums) {
            xor ^= n;
        }
        // lowbit是所有数异或结果仅保留最低位1其余全是0对应的值，a、b在此位上异或结果为1说明a、b在此位的值肯定不同，那么我们就可以利用此位将a、b两数分开
        int lowbit = xor & (-xor);
        // 所有数和lowbit按位与，根据在此位是1还是0分到两个子数组中，则a、b肯定分到了不同的子数组，同值的肯定也都在同一个子数组
        // 则问题转变为两个 "数组中所有值都出现2次只有一个值出现1次" 的问题，子数组所有值异或可分别得到a、b值
        int a = 0, b = 0;
        for (int n : nums) {
            if ((n & lowbit) == 0) {
                a ^= n;
            } else {
                b ^= n;
            }
        }
        int[] res = new int[]{a, b};
        return res;
    }
}

---

GitHub代码

algorithms/leetcode/leetcode/_260_SingleNumber3.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_260_SingleNumber3.java

---