LeetCode 260. 只出现一次的数字 III

Categories:

题目描述
思路分析
1. 解法一：位运算（异或分组）（推荐）
相似题目

题目描述

✅ 260. 只出现一次的数字 III

思路分析

解法一：位运算（异或分组）（推荐）

核心思路：

将数组中所有元素异或，得到 xor = a ^ b（因为出现两次的数相互抵消）。

xor 中某一位为 1，说明 a 和 b 在该位上不同。取最低位 mask = xor & (-xor)。

按照 mask 位是否为 1 将数组分成两组，每组分别异或，即可分别得到 a 和 b。

复杂度分析：

时间复杂度：O(n)，其中 n 表示数组长度，遍历两次数组。

空间复杂度：O(1)，只使用常数额外空间。

class Solution {
    public int[] singleNumber(int[] nums) {
        // 第一步：全部异或，得到两个目标数的异或值
        int xor = 0;
        for (int num : nums) {
            xor ^= num;
        }
        // 取最低位的 1，用于区分两个目标数
        int mask = xor & (-xor);
        int a = 0, b = 0;
        // 第二步：按 mask 位分组异或，分别还原两个目标数
        for (int num : nums) {
            if ((num & mask) == 0) {
                a ^= num;
            } else {
                b ^= num;
            }
        }
        return new int[]{a, b};
    }
}

func singleNumber(nums []int) []int {
	// 第一步：全部异或，得到两个目标数的异或值
	xor := 0
	for _, num := range nums {
		xor ^= num
	}
	// 取最低位的 1，用于区分两个目标数
	mask := xor & (-xor)
	a, b := 0, 0
	// 第二步：按 mask 位分组异或，分别还原两个目标数
	for _, num := range nums {
		if (num & mask) == 0 {
			a ^= num
		} else {
			b ^= num
		}
	}
	return []int{a, b}
}

相似题目

题目	难度	考察点
136. 只出现一次的数字	简单	位运算 / 异或
137. 只出现一次的数字 II	中等	位运算 / 状态机
268. 丢失的数字	简单	位运算 / 数学
389. 找不同	简单	位运算 / 异或
645. 错误的集合	简单	哈希表 / 位运算
1442. 形成两个异或相等数组的三元组数目	中等	位运算 / 异或

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/16345207