当前位置：首页 > news >正文

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

news 2025/7/17 10:53:32

一、题目描述

给你一个整数数组 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。

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

以下是具体的解题步骤：

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

三、具体代码

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。