LeetCode_位运算_中等_260.只出现一次的数字 III

悠悠 2023-10-06 23:28 16阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。找出只出现一次的那两个元素。你可以按任意顺序返回答案。

**进阶：你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？**

**示例 1：**  
输入：nums = \[1,2,1,3,2,5\]  
输出：\[3,5\]  
解释：\[5, 3\] 也是有效的答案。

**示例 2：**  
输入：nums = \[-1,0\]  
输出：\[-1,0\]

**示例 3：**  
输入：nums = \[0,1\]  
输出：\[1,0\]

**提示：**  
2 <= nums.length <= 3 \* 104  
\-231 <= nums\[i\] <= 231 \- 1  
除两个只出现一次的整数外，nums 中的其他数字都出现两次

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/single-number-iii

## 2.思路 ##

（1）哈希表  
如果使用额外空间的话，比较容易想到的是使用哈希表，先将数组中的所有元素添加到 hashMap 中（键/值为元素值/该元素出现的次数），然后再在哈希表中找出只出现了一次的元素并将其返回即可。

（2）位运算  
思路参考[该 LeetCode 用户题解][LeetCode]。

下面举个例子来说明该方法的过程：  
① 假设数组 nums = \{1, 2, 1, 3, 2, 5\}，其中的元素对应的二进制数分别为：

0000...0001
    0000...0010
    0000...0001
    0000...0011
    0000...0010
    0000...0101

将它们进行异或操作，得到的结果为 xorSum = 1 ^ 2 ^ 1 ^ 3 ^ 2 ^ 5 = 3 ^ 5 = (0000…0011 ^ 0000…0101) = 0000…0110。由于除两个只出现一次的整数外，数组 nums 中的其他数字都出现两次，并且**两个相同的数的异或操作的结果为 0，所以 xorSum 就可以看作是两个只出现一次的整数的异或值**。

② 现在任取 xorSum 二进制表示中为 1 一位 k，例如 k = 2（即 xorSum 的二进制表示的第 2 位为 1，从右往左开始计数，下标从 0 开始），这意味着**数组 nums 中只出现了一次的元素的二进制表示的第 k 位不相同**，此处对应 0000…0011 和 0000…0101。

③ 对 nums 进行遍历，对第 k 位分别为 0 和 1 的元素分别求异或和，这样两答案必然会被分到不同的组，具体过程如下：

数组 nums 中二进制表示的第 2 位为 0 的元素有 1, 2, 1, 3, 2
    数组 nums 中二进制表示的第 2 位为 1 的元素有 5
    1 ^ 2 ^ 1 ^ 3 ^ 2 = 3
    5 = 5
    由于对于任意数 a，a ^ 0 = a，所以为了方便保存结果，可先定义长度为 2 的结果数组 res，其初始值均为 0，那么
    res[0] = res[0] ^ 1 ^ 2 ^ 1 ^ 3 ^ 2 = 3
    res[1] = res[1] ^ 5 = 5
    这样便找到了数组 nums 中只出现一次的两个元素！

相关题目：  
[LeetCode\_位运算\_简单\_136.只出现一次的数字][LeetCode_136.]  
[LeetCode\_位运算\_中等\_137.只出现一次的数字 II][LeetCode_137._ II]

## 3.代码实现（Java） ##

//思路1————哈希表
    class Solution {
        
        public int[] singleNumber(int[] nums) {
        
            HashMap<Integer, Integer> hashMap = new HashMap<>();
            for (int i = 0; i < nums.length; i++) {
        
                hashMap.put(nums[i], hashMap.getOrDefault(nums[i], 0) + 1);
            }
            int cnt = 0;
            int[] res = new int[2];
            for (Integer num : hashMap.keySet()) {
        
                if (hashMap.get(num) == 1) {
        
                    res[cnt++] = num;
                }
            }
            return res;
        }
    }

//思路2————位运算
    class Solution {
        
        public int[] singleNumber(int[] nums) {
        
            int[] res = new int[2];
            int xorSum = 0;
            for (int num : nums) {
        
                xorSum ^= num;
            }
            int k = -1;
            for (int i = 0; i < 31; i++) {
        
                if (((xorSum >> i) & 1) == 1) {
        
                    k = i;
                    break;
                }
            }
            for (int num : nums) {
        
                if (((num >> k) & 1) == 0) {
        
                    res[0] ^= num;
                } else {
        
                    res[1] ^= num;
                }
            }
            return res;
        }
    }

[LeetCode]: https://leetcode.cn/problems/single-number-iii/solution/gong-shui-san-xie-yi-ti-shuang-jie-ha-xi-zgi4/
[LeetCode_136.]: https://blog.csdn.net/weixin_43004044/article/details/120247699
[LeetCode_137._ II]: https://blog.csdn.net/weixin_43004044/article/details/126020515