0136.只出现一次的数字

难度：🟢 简单

标签：位运算、数组、哈希表

链接：136. 只出现一次的数字

题目描述

给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现一个时间复杂度为 O(n) 的线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

示例 1 ：

输入：nums = [2,2,1]
输出：1

示例 2 ：

输入：nums = [4,1,2,1,2]
输出：4

示例 3 ：

输入：nums = [1]
输出：1

解题思路

核心思想

本题的核心是在一个数组中，找出唯一一个出现奇数次（一次）的元素，而其他所有元素都出现偶数次（两次）。解决这个问题的最巧妙方法是利用 按位异或（XOR） 运算的特性。

思路选择

位运算法 是解决此问题的最优思路，因为它能同时满足线性和时间复杂度和常数空间复杂度的要求。

• 异或运算有两个关键性质：

  1. 任何数与 0 进行异或运算，结果仍然是原来的数，即 a ^ 0 = a。

  2. 任何数与自身进行异或运算，结果是 0，即 a ^ a = 0。

• 基于这些性质，我们可以将数组中所有的数字进行异或运算。成对出现的数字会因为 a ^ a = 0 而相互抵消。最终，整个数组的异或结果就等于那个只出现一次的数字与 0 的异或结果，也就是那个数字本身。

关键步骤

1. 初始化：初始化一个变量 result 为 0（或者直接用数组的第一个元素 nums[0] 开始）。

2. 循环遍历：遍历整个数组 nums。

3. 累积异或：在循环中，将 result 与当前遍历到的元素 nums[i] 进行按位异或运算，并将结果存回 result。

4. 返回结果：遍历结束后，result 中存储的就是那个只出现一次的数字。

代码实现

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function(nums) {
    // 初始化结果为第一个元素
    let result = nums[0];

    // 从第二个元素开始，将所有元素进行异或运算
    for(let i = 1; i < nums.length; i++){
        result ^= nums[i];
    }

    // 最终结果即为只出现一次的数字
    return result;
};

复杂度分析

• 时间复杂度：O(n) 其中 n 是数组 nums 的长度。我们只需要对数组进行一次完整的遍历。

• 空间复杂度：O(1) 我们只使用了一个额外的变量 result 来存储中间结果，空间消耗是恒定的。

相关题目

• 0137.只出现一次的数字 II

• 0260.只出现一次的数字 III

• 0268.丢失的数字

总结

本题是位运算应用的典范。通过利用异或运算的交换律和结合律，以及其独特的“相同为0，不同为1”的特性，我们能够以一种极为优雅和高效的方式解决这个问题。这充分展示了在特定场景下，位运算相比传统算法的巨大优势。