LeetCode.剑指offer.056.数组中数字出现的次数

题目描述

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

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

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

示例 1：

输入：nums = [4,1,4,6]
输出：[1,6] 或 [6,1]

示例 2：

输入：nums = [1,2,10,4,1,4,3,3]
输出：[2,10] 或 [10,2]

限制： 2 <= nums <= 10000

---

相似题目

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

---

解题过程

一看题有印象做过，貌似是用位运算，但具体怎么做已经忘了，想了一会儿想出来了。
看来做题还是有用的，即便忘了也比没做过要强。

假如只出现一次的数为 a 和 b
思路是想一个办法把 a,b 拆分到两个数组中，然后变成了2个其他元素出现2次只有一个出现一次的子问题，直接异或即可。

怎么才能把 a,b 区分开呢？
我们求所有元素的异或值，则结果是 a^b ，因为所有其他元素都两两消掉了，因为 a 和 b 肯定不相同，所以 a^b 不是0，则可以用 a^b 的二进制表示的某个值是1的位来把 a b 区分开，

比如可以取 a^b 的最低位1，则
1、对于a,b来说，肯定在这个二进制位上是不同的，因为异或的计算规则是相同为0，不同为1
2、对于所有其他两两元素来说，相同的2个数在这个二进制位上肯定是相同的

具体实现上
我们利用公式 lowbit(i) = i & -i; 得到 a^b 的保留最低位1其余全为0对应的整数，则
数组中所有元素和 lowbit 进行 按位与的结果等于 lowbit 的是一组，不等于 lowbit 的是另一组，
则a,b肯定在这两个不同组中，对这两组所有元素分别异或，分别得到的就是a,b的值

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

private static class SolutionV2020 {
    public int[] singleNumbers(int[] nums) {
        if (null == nums || nums.length < 2) {
            return nums;
        }
        // 所有元素的异或，就等于出现1次的两个数的异或
        int xor = nums[0];
        for (int i = 1; i < nums.length; i++) {
            xor ^= nums[i];
        }
        // 获取 xor 的最低位1其余全0对应的整数，牢记这个公式
        int lowest1 = xor & (-xor);
        // 根据 nums[i] 在 lowest1 位上是1还是0把数组中的数分为2组同时做异或，出现次数为1的两个数肯定在不同组中，其他的相同的元素肯定在同一组中
        int group1 = 0, group2 = 0;
        for (int i = 0; i < nums.length; i++) {
            if ((lowest1 & nums[i]) == lowest1) {
                group1 ^= nums[i];
            } else {
                group2 ^= nums[i];
            }
        }
        return new int[] {group1, group2};
    }
}

---

GitHub代码

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

---