LeetCode 补充题 115. 其余元素出现 k 次的唯一数
题目描述
:::fold-green 相关原题
LeetCode 原题： ✅ 137. 只出现一次的数字 II
LeetCode 原题中其余元素均出现 3 次；本文将重复次数推广为参数 k。
:::
给你一个 32 位有符号整数数组
nums和整数k。数组中恰好有一个数出现一次，其余每个不同的数都出现k次。请返回只出现一次的那个数。
示例 1：
输入：
nums = [-7,2,2,2,2], k = 4
输出：-7
解释： 2 出现 4 次，只有 -7 出现一次。
示例 2：
输入：
nums = [5,1,1], k = 2
输出：5
解释： 1 出现两次，5 出现一次。
提示：
1 <= n <= 2*10^51 < k < 100-2*10^9 <= arr[i] <= 2*10^9
题意分析
异或只能直接消去偶数次重复，而这里的重复次数
k不固定。将整数拆成独立的二进制位后，每个重复数对某一位贡献 0 或k个 1，可以通过对k取余统一消去。
解法：逐位计数对 k 取余
核心思路
[!blue]
对位
bit，累加所有数该位上的 1，得到count。除唯一数外，每个不同数都完整出现k次，所以它们的总贡献是k的倍数；count % k恰好是唯一数的这一位，只可能为 0 或 1。从第 0 位到第 31 位重复统计，将余数为 1 的位写回结果，就完整恢复了唯一数的补码。符号位也必须统计，不能只处理正数的有效位。
Java 用无符号右移提取各位，最后
int自然按有符号补码解释。Go 先转成uint32提取和拼接，再经int32恢复符号，避免在 64 位平台上把负数结果当成大正数。
解题步骤
- 遍历32个二进制位，统计输入中该位的1。
- 每位计数对k取模，拼回唯一数的对应位。
- 按照32位有符号补码返回结果。
代码实现
class Solution {
public int singleNumber(int[] nums, int k) {
if (k <= 1) {
throw new IllegalArgumentException("k must exceed one");
}
int result = 0;
for (int bit = 0; bit < 32; bit++) {
int count = 0;
for (int x : nums) {
count += (x >>> bit) & 1;
}
if (count % k != 0) {
result |= 1 << bit;
}
}
return result;
}
}
func singleNumber(nums []int, k int) int {
if k <= 1 {
panic("k must exceed one")
}
var result uint32
for bit := uint(0); bit < 32; bit++ {
count := 0
for _, x := range nums {
count += int((uint32(x) >> bit) & 1)
}
if count%k != 0 {
result |= uint32(1) << bit
}
}
return int(int32(result))
}
复杂度分析
- 时间复杂度：$O(32n)$，即 $O(n)$。
- 空间复杂度：额外空间 $O(1)$。
关键点总结
[!green]
重复k次的每个数在每一位的贡献都能消去，余数只来自唯一数；重建第31位时保留原始补码；Go先拼uint32，再转int32恢复符号。
易错点总结
[!yellow]
保留负数的符号位；输入条件必须是其余每个数恰好出现k次；不能照搬只适用于3次的固定状态机。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 137. 只出现一次的数字 II | 中等 | 将其他数出现三次推广为出现 k 次，逐位贡献消去仍成立，固定三态机则不能原样套用。 |
| 136. 只出现一次的数字 | 简单 | k=2 时可简化为异或抵消；一般 k 需要按位统计并取模。 |