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

痛定思痛。 2023-10-06 23:28 6阅读 0赞

#### 目录 ####

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

## 1.题目 ##

**给你一个整数数组 nums ，除某个元素仅出现一次外，其余每个元素都恰出现三次 。请你找出并返回那个只出现了一次的元素。**

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

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

**提示：**  
1 <= nums.length <= 3 \* 104  
\-231 <= nums\[i\] <= 231 \- 1  
nums 中，除某个元素仅出现一次外，其余每个元素都恰出现三次

**进阶：你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？**

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

## 2.思路 ##

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

（2）哈希集合  
先用集合 hashSet 来存储数组 nums 中出现的所有元素，并且计算数组 nums 中的所有元素之和。又由于集合元素的无重复性，所以集合 hashSet 中的所有元素之和的三倍就是数组 nums 中每个元素出现三次的情况下的元素之和。又由题目可知，数组 nums 中只有一个元素出现一次，其余元素都出现三次，所以**只出现一次的元素值 = (nums 中所有非重复元素之和 \* 3 - nums的所有元素之和) / 2**。不过在编写时需要注意 int 整数溢出的问题！

（3）位运算  
使用长度为 32 的数组 cnt 来记录数组 nums 中所有元素对应的二进制位的每一位出现的 1 的总次数，然后再对数组 cnt 中的每一个元素值进行 mod 3 操作，将拼接出的结果即为数组 nums 中只出现一次的元素。为了方便理解，以下面的例子来介绍：

① 假设数组 nums = \{2, 2, 3, 2, 5, 5, 5\}，其中的元素对应的二进制数分别为：

00...010
    00...010
    00...011
    00...010
    00...101
    00...101
    00...101

② 通过计算可知 cnt = \{0, 0, …, 3, 4, 4\}，以 cnt\[31\] = 4 为例，它表示 2, 2, 3, 2, 5, 5, 5 对应的二进制数的最低位一共有 4 个 1。

③ 由于数组 nums 中，除某个元素仅出现一次外，其余每个元素都恰出现三次，那么这说明出现三次的元素所对应的二进制数的每一位也出现了 3 次，这反应到数组 cnt 中的情况就是 cnt\[i\] == k \* 3 + 1/0，其中 k 表示当二进制位为 1 的且出现三次的元素的个数，所以对数组 cnt 中的每一个元素进行 mod 3 操作后得到 \{0, 0, …, 0, 1, 1\}，显然将 0, 0, …, 1, 1 拼接后得到的数为只出现一次的元素所对应的二进制数，即 Nums 中的 3。

另外，该算法的时间复杂度为 O(n)，空间复杂度为 O(1)。

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

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

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

//思路2————哈希集合
    class Solution {
        
        public int singleNumber(int[] nums) {
        
            HashSet<Integer> hashSet = new HashSet<>();
            long sum = 0;
            for (int num : nums) {
        
                hashSet.add(num);
                //计算数组 nums 中所有元素之和
                sum += (long)num;
            }
            long setSum = 0;
            for (Integer num : hashSet) {
        
                //计算数组 nums 中所有非重复元素之和
                setSum += (long)num;
            }
            return (int)((3 * setSum - sum) / 2);
        }
    }

//思路3————位运算
    class Solution {
        
        public static int singleNumber(int[] nums) {
        
            int res = 0;
            //记录下所有数值的每一位共出现了多少次 1
            int[] cnt = new int[32];
            for (int num : nums) {
        
                for (int i = 0; i < 32; i++) {
        
                    /*
                        (1) num >> i: num 对应的二进制数的所有二进制为均向右移 i 位;
                        (2) (num >> i) & 1: 获取 num >> i 的二进制数的最低位;
                    */
                    if (((num >> i) & 1) == 1) {
        
                        cnt[i]++;
                    }
                }
            }
            for (int i = 0; i < 32; i++) {
        
                if (cnt[i] % 3 == 1) {
        
                	//拼接结果
                    res += (1 << i);
                }
            }
            return res;
        }
    }

> 有关移位运算符的相关知识可以参考 [Java 基础面试题——运算符][Java]这篇文章。

[LeetCode_136.]: https://blog.csdn.net/weixin_43004044/article/details/120247699
[LeetCode_260._ III]: https://blog.csdn.net/weixin_43004044/article/details/126021467
[Java]: https://xgqngu.blog.csdn.net/article/details/129033512