LeetCode 136. 只出现一次的数字

Categories:

Tags:

题目描述
思路分析
1. 解法一：位运算（异或，推荐）
2. 解法二：哈希集合
相似题目

题目描述

✅ 136. 只出现一次的数字

思路分析

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

核心思路：

利用异或运算的三个核心性质：

a ^ a = 0：相同的两个数异或结果为 0

a ^ 0 = a：任意数与 0 异或结果为其自身

异或满足交换律和结合律：运算顺序不影响结果

将数组所有元素依次异或，出现两次的数字两两抵消变为 0，最终剩下的就是只出现一次的数字。

举例：[4, 1, 2, 1, 2]
4 ^ 1 ^ 2 ^ 1 ^ 2
= 4 ^ (1 ^ 1) ^ (2 ^ 2)   // 利用交换律与结合律重排
= 4 ^ 0 ^ 0 = 4
复杂度分析：

时间复杂度：O(n)，其中 n 为数组长度，需遍历数组一次

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

class Solution {
    public int singleNumber(int[] nums) {
        int res = 0;
        // 所有数异或，出现两次的数字相互抵消，剩余即为单独数字
        for (int num : nums) {
            res ^= num;
        }
        return res;
    }
}

func singleNumber(nums []int) int {
    res := 0
    // 所有数异或，出现两次的数字相互抵消，剩余即为单独数字
    for _, num := range nums {
        res ^= num
    }
    return res
}

解法二：哈希集合

核心思路：

使用哈希集合记录每个数字的出现情况：

若当前数字已在集合中，说明出现了第二次，将其从集合中删除

若当前数字不在集合中，将其加入集合

遍历结束后，集合中唯一剩余的元素即为只出现一次的数字。

复杂度分析：

时间复杂度：O(n)，其中 n 为数组长度，需遍历数组一次

空间复杂度：O(n)，其中 n 为数组长度，哈希集合最多存储 n/2 个元素

class Solution {
    public int singleNumber(int[] nums) {
        Set<Integer> seen = new HashSet<>();
        for (int num : nums) {
            // 第二次出现则移除，第一次出现则加入
            if (!seen.add(num)) {
                seen.remove(num);
            }
        }
        return seen.iterator().next();
    }
}

func singleNumber(nums []int) int {
    seen := map[int]struct{}{}
    for _, cur := range nums {
        // 第二次出现则从集合中删除，第一次出现则加入集合
        if _, exists := seen[cur]; exists {
            delete(seen, cur)
        } else {
            seen[cur] = struct{}{}
        }
    }
    for key := range seen {
        return key
    }
    return 0
}

相似题目

题目	难度	考察点
137. 只出现一次的数字 II	中等	位运算、状态机
260. 只出现一次的数字 III	中等	位运算、分组异或
268. 丢失的数字	简单	位运算、数学
645. 错误的集合	简单	哈希、位运算
287. 寻找重复数	中等	位运算、Floyd 判环
389. 找不同	简单	位运算、异或
540. 有序数组中的单一元素	中等	二分查找、位运算

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/84719035