ChunNote
0%

leetCode-260:Single Number III

发表于 分类于

问题描述

给定一个整数数组，数组中的数字有两个只出现一次，其他数字出现两次。要求在时间复杂度 O(n)、空间复杂度 O(1) 的情况下将这两个数字找出来。题目链接：**点我**

样例输入输出

输入：[1, 2, 1, 3, 2, 5]

输出：[3, 5]

输入：[1, 3]

输出：[1, 3]

问题解法

此题最简单的做法是用 map 来存储数字出现的次数，但是这需要耗费 O(n) 的空间，不满足题目要求。因此需要考虑位运算的解法，此解法参考：https://leetcode-cn.com/problems/single-number-iii/solution/cai-yong-fen-zhi-de-si-xiang-jiang-wen-ti-jiang-we/。具体做法是：先将数组中数字进行异或运算，得到两个出现一次的数字 A、B 的异或值 X，因为 A、B 不相等，所以 X 不等于 0，那 X 必然存在至少一个位数为 1，根据 x & (-x) 可以获得 X 的最低位为 1 的数，记为 mask，此时对数组中的每个数分别与 mask 进行与运算，可以将原数组分成两个部分：一个是结果为 0 的子数组，一个是结果为 1 的子数组。此时，数字相同（出现两次）的会被分配到同一个子数组中，而 A 和 B（只出现一次的数字）必然分配到不同的子数组中（因为是按照 A 和 B 的异或值的某一位为 1 来区分的）。可以看出，此时两个子数组的特点：只有一个数字出现一次，其他数字出现两次。那么此时求解就可以简化成：在两个子数组中，分别找出只出现一次的数字。

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int[] singleNumber(int[] nums) {
        int xorNum = 0;
        for (int num : nums) {
            xorNum ^= num;
        }
        
        int temp = xorNum & (-xorNum);
        int[] result = new int[2];
        for (int num : nums) {
            if ((num & temp) == 0) {
                result[0] ^= num;
            } else {
                result[1] ^= num;
            }
        }
        
        return result;
    }
}

参考资料

https://leetcode-cn.com/problems/single-number-iii/solution/cai-yong-fen-zhi-de-si-xiang-jiang-wen-ti-jiang-we/