LeetCode 补充题 192. 数组中两个只出现一次的数
题目描述
:::fold-green 相关原题
LeetCode 原题： ✅ 260. 只出现一次的数字 III
力扣允许任意顺序返回两个答案；本文额外要求按升序返回。
:::
整数数组
nums中恰有两个值各出现一次，其余值均出现两次。按升序返回这两个只出现一次的值。
示例 1：
输入：
nums = [3,1,2,1]
输出：[2,3]
提示：
- 数组满足上述出现次数约定。
- 元素为
32位整数。
题意分析
全体异或能消除出现两次的值，却只能得到两个答案的异或，不能直接恢复各自的值。需要找到它们不同的一位，把两个答案分开，同时让每对重复值仍在同一组中抵消。
解法：异或分组
核心思路
[!blue]
先把所有数异或，成对出现的值互相抵消，只剩两个答案的异或
xor。两个答案不同，所以 xor 至少有一个为 1 的位；xor & -xor取出其中最低的一位。这一位为 1 说明两个答案在该位不同。按这个位分组后，它们分别落入两组；每个重复值的两次出现仍在同一组，继续异或就各自消去。代码只求一组的
first，另一组答案直接为xor ^ first。分组顺序与数值大小无关，最后再取两个值的最小、最大值，满足升序返回要求。
解题步骤
- 异或全部元素，得到两个答案的异或值 xor。
- 用 xor & -xor 取最低非零位，作为分组标记。
- 异或该位为 0 的所有元素得到 first，再用 xor ^ first 得到另一个答案。
- 按数值大小排列两个答案后返回。
代码实现
class Solution {
public int[] singleNumber(int[] nums) {
int xor = 0;
for (int num : nums) {
xor ^= num;
}
int lowbit = xor & -xor;
int first = 0;
for (int num : nums) {
if ((num & lowbit) == 0) {
first ^= num;
}
}
int second = xor ^ first;
return new int[] {
Math.min(first, second),
Math.max(first, second)
};
}
}
func singleNumber(nums []int) []int {
xor := 0
for _, num := range nums {
xor ^= num
}
lowbit := xor & -xor
first := 0
for _, num := range nums {
if num&lowbit == 0 {
first ^= num
}
}
second := xor ^ first
return []int{
min(first, second),
max(first, second),
}
}
复杂度分析
- 时间复杂度：$O(n)$。
- 空间复杂度：额外空间 $O(1)$，不计两个返回值。
关键点总结
[!green]
全体异或得到两个答案的异或值，选取其中一个非零位分组，组内重复数抵消；最后对两个结果取最小值和最大值。
易错点总结
[!yellow]
- 两个答案不同，保证 xor 非零，才能找到用于分组的位。
- 按同一位是否为 0 分组，负数也适用，不要改成按正负分组。
- 分组顺序不代表数值大小，返回前仍需排序。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 260. 只出现一次的数字 III | 中等 | 异或分组消去成对元素的过程相同；该题允许任意顺序返回两个唯一值，本题要求升序输出。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！