LeetCode题练习与总结：只出现一次的数字Ⅱ--137

一、题目描述

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

你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。

示例 1：

输入：nums = [2,2,3,2]
输出：3

示例 2：

输入：nums = [0,1,0,1,0,1,99]
输出：99

提示：

• 1 <= nums.length <= 3 * 10^4
• -2^31 <= nums[i] <= 2^31 - 1
• nums 中，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次

二、解题思路

这个问题是一个典型的位操作问题。由于每个元素都出现了三次，除了一个元素只出现了一次，我们可以考虑每个元素的每一位。如果将所有元素在每个位上累加起来，那么每个位上的和应该是3的倍数。如果有任何位上的和不是3的倍数，那么只出现一次的元素在该位上必须是1。

例如，假设数组是 [2,2,3,2]（二进制表示为 [10, 10, 11, 10]）：

• 在第一位（最右边）上，所有数的和是 1+1+1+1 = 4，不是3的倍数，这意味着只出现一次的数的第一位是1。
• 在第二位上，所有数的和是 0+0+1+0 = 1，不是3的倍数，这意味着只出现一次的数的第二位是1。

所以，只出现一次的数是 11，即 3。

我们可以用这样的方法检查每个位，然后重构出只出现一次的数。

以下是具体的解题步骤：

1. 初始化一个长度为32的数组（因为一个整数的二进制表示最多有32位）来存储每一位的和。
2. 遍历数组 nums 中的每个数，对于每个数，检查其二进制表示的每一位，如果是1，则将对应位的和加1。
3. 遍历完成后，检查每一位的和，如果不是3的倍数，那么只出现一次的数在该位上是1。
4. 根据这些信息，重构出只出现一次的数。

三、具体代码

class Solution {public int singleNumber(int[] nums) {int[] count = new int[32]; // 32位整数for (int num : nums) {for (int i = 0; i < 32; i++) {count[i] += (num >> i) & 1; // 检查num的第i位是否为1}}int result = 0;for (int i = 0; i < 32; i++) {// 如果count[i]不是3的倍数，那么result的第i位是1result |= (count[i] % 3) << i;}return result;}
}

四、时间复杂度和空间复杂度

1. 时间复杂度

• 遍历数组 nums 中的每个元素是一个 O(n) 操作，其中 n 是数组 nums 的长度。
• 对于每个元素，我们检查它的每一位，这是一个 O(1) 操作，因为一个整数的位数是固定的，最多为 32 位。
• 因此，外层循环的时间复杂度是 O(n)，内层循环的时间复杂度是 O(1)，所以总的时间复杂度是 O(n)。

2. 空间复杂度

• 我们使用了一个长度为 32 的数组 count 来存储每一位的和，这是一个固定大小的数组，不随输入数组 nums 的大小而变化。
• 因此，空间复杂度是 O(1)，即常数空间复杂度。

综上所述，给定代码的时间复杂度是 O(n)，空间复杂度是 O(1)。这满足了题目要求的线性时间复杂度和常数空间复杂度。

五、总结知识点

1. 位操作：

• >>：右移操作符，用于将一个数的二进制表示向右移动指定的位数。例如，num >> i 表示将 num 的二进制表示向右移动 i 位。
• &：按位与操作符，用于对两个数的二进制表示进行逐位比较，只有两个位都是1时，结果位才是1。在这里，(num >> i) & 1 用于检查 num 的第 i 位是否为1。
• |：按位或操作符，用于对两个数的二进制表示进行逐位比较，只要有一个位是1，结果位就是1。在这里，result |= (count[i] % 3) << i 用于将 result 的第 i 位设置为1，如果 count[i] % 3 不为0。

2. 数组的初始化和使用：

• int[] count = new int[32];：初始化一个长度为32的整数数组，用于存储每一位的和。

3. 循环结构：

• for (int num : nums)：这是Java中的增强型for循环，用于遍历数组 nums 中的每个元素。
• for (int i = 0; i < 32; i++)：这是一个传统的for循环，用于重复执行32次，每次循环处理一个二进制位。

4. 取模运算：

• %：取模运算符，用于计算一个数除以另一个数后的余数。在这里，count[i] % 3 用于检查 count[i] 是否是3的倍数。

5. 位掩码：

• 1 << i：创建一个只在第 i 位上为1的位掩码。这个掩码用于将 count[i] % 3 的结果放到 result 的正确位置上。

以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。