【LeetCode 热题 100】136. 只出现一次的数字——异或

发布于:2025-07-10 ⋅ 阅读:(19) ⋅ 点赞:(0)

Problem: 136. 只出现一次的数字
题目:给你一个 非空 整数数组 nums ,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题,且该算法只使用常量额外空间。

整体思路

这段代码旨在解决一个非常经典的位运算问题:只出现一次的数字 (Single Number)。问题要求在一个非空整数数组中,除了某个元素只出现一次以外,其余每个元素均出现两次。目标是找出那个只出现了一次的元素。

该算法利用了 异或(XOR) 运算的两个关键性质,以一种极其巧妙和高效的方式解决了这个问题:

  1. 异或运算的核心性质

    • 任何数与 0 异或,结果是其本身a ^ 0 = a
    • 任何数与自身异或,结果是 0a ^ a = 0
    • 异或运算满足交换律和结合律a ^ b ^ a = (a ^ a) ^ b = 0 ^ b = b
  2. 算法逻辑

    • 初始化:算法初始化一个变量 ans 为 0。根据性质1,ans 的初始值不会影响后续的异或结果。
    • 累积异或:算法遍历数组中的每一个元素 x,并将其与 ans 进行异或运算,然后将结果存回 ans。即 ans = ans ^ x
    • 最终结果:当遍历完整个数组后,ans 中存储的就是最终的答案。
  3. 为什么这样可行?

    • 假设数组是 [a, b, a, c, c]
    • 整个异或过程可以看作是 ans = 0 ^ a ^ b ^ a ^ c ^ c
    • 根据交换律和结合律,这个表达式等价于 ans = (a ^ a) ^ (c ^ c) ^ b ^ 0
    • 根据性质2,a ^ a = 0c ^ c = 0
    • 所以表达式变为 ans = 0 ^ 0 ^ b ^ 0
    • 根据性质1,最终 ans = b
    • 这个过程可以推广到任意数组:所有出现两次的数,在累积异或的过程中都会两两配对,最终结果变为 0。而那个只出现一次的数,无法找到配对,最终会与一个 0 进行异或,从而保留其自身的值。

这个算法构思极为精妙,完美地利用了位运算的特性,提供了一个既不需要额外空间,又具有线性时间复杂度的解决方案。

完整代码

class Solution {
    /**
     * 在一个非空整数数组中,找出那个只出现一次的元素。
     * 数组中其余每个元素均出现两次。
     * @param nums 输入的整数数组
     * @return 只出现一次的那个元素
     */
    public int singleNumber(int[] nums) {
        // ans 用于累积所有元素的异或结果。
        // 初始化为 0,因为任何数与 0 异或都等于其本身 (a ^ 0 = a)。
        int ans = 0;
        
        // 遍历数组中的每一个元素 x
        for (int x : nums) {
            // 将当前元素 x 与累积结果 ans 进行异或运算。
            // 核心原理:
            // 1. a ^ a = 0 (任何数与自身异或为 0)
            // 2. a ^ b ^ a = b (交换律和结合律)
            // 所有出现两次的数字在异或过程中会两两抵消为 0。
            // 最终只剩下那个只出现一次的数字与 0 进行异或,结果就是它本身。
            ans ^= x;
        }
        
        // 返回最终的累积异或结果,即为只出现一次的数字。
        return ans;
    }
}

时空复杂度

时间复杂度:O(N)

  1. 循环:算法的核心是一个 for-each 循环,它遍历 nums 数组中的每一个元素一次。如果数组的长度为 N,这个循环将执行 N 次。
  2. 循环内部操作
    • 在循环的每一次迭代中,只执行了一次异或运算 (^=)。
    • 这是一个基本的位运算,时间复杂度是 O(1)

综合分析
算法由 N 次 O(1) 的操作组成。因此,总的时间复杂度是 N * O(1) = O(N)

空间复杂度:O(1)

  1. 主要存储开销:算法只使用了 ansx 等几个整型变量来存储状态。
  2. 空间大小:这些变量的数量是固定的,与输入数组 nums 的大小 N 无关。

综合分析
算法没有使用任何与输入规模 N 成比例的额外数据结构(如新数组或哈希表)。因此,其额外辅助空间复杂度为 O(1)。这是一个在时间和空间上都达到最优的解决方案。

参考灵神


网站公告

今日签到

点亮在社区的每一天
去签到