LeetCode 题解工作台
只出现一次的数字 II
给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。 请你找出并返回那个只出现了一次的元素。 你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。 示例 1： 输入： nums = [2,2,3,2] 输出： 3 示例 2： 输入： nums = […
2
题型
9
代码语言
3
相关题
当前训练重点
中等 · 数组·结合·位运算·操作
答案摘要
我们可以枚举每个二进制位 ，对于每个二进制位，我们统计所有数字在该二进制位上的和，如果该二进制位上的和能被 整除，那么只出现一次的数字在该二进制位上为 ，否则为 。 时间复杂度 $O(n \times \log M)$，空间复杂度 。其中 和 分别是数组的长度和数组中元素的范围。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·结合·位运算·操作 题型思路
题目描述
给你一个整数数组 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 - 1nums中，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次
解题思路
方法一：位运算
我们可以枚举每个二进制位 ，对于每个二进制位，我们统计所有数字在该二进制位上的和，如果该二进制位上的和能被 整除，那么只出现一次的数字在该二进制位上为 ，否则为 。
时间复杂度 ，空间复杂度 。其中 和 分别是数组的长度和数组中元素的范围。
class Solution:
def singleNumber(self, nums: List[int]) -> int:
ans = 0
for i in range(32):
cnt = sum(num >> i & 1 for num in nums)
if cnt % 3:
if i == 31:
ans -= 1 << i
else:
ans |= 1 << i
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Look for an efficient solution using bit manipulation techniques to handle large arrays within time and space constraints.
- question_mark
Candidates should avoid using hashmaps or arrays, focusing instead on bitwise operations to solve the problem.
- question_mark
Pay attention to how well the candidate handles the edge cases and optimizes the solution for constant space usage.
常见陷阱
外企场景- error
Relying on hashmaps or arrays, which violate the constant space requirement.
- error
Not correctly handling the bitwise operations, leading to incorrect results when tracking occurrences of the bits.
- error
Failing to consider edge cases such as when the array has only one element or all elements are negative.
进阶变体
外企场景- arrow_right_alt
Implementing the solution using a different set of bitwise operations or bit tracking techniques.
- arrow_right_alt
Using different approaches like mathematical formulas or recursion instead of bit manipulation.
- arrow_right_alt
Handling arrays of varying sizes and input constraints, ensuring the solution works under all edge cases.