当前位置：首页 > news >正文

只出现一次的数字（字节面试题最优解）

news 来源：原创 2025/6/23 1:01:53

题目来源

136. 只出现一次的数字 - 力扣（LeetCode）

题目描述

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

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

示例 1 ：
输入：nums = [2,2,1]
输出：1
示例 2 ：
输入：nums = [4,1,2,1,2]
输出：4
示例 3 ：
输入：nums = [1]
输出：1
提示：

1 <= nums.length <= 3 * 104
-3 * 104 <= nums[i] <= 3 * 104
除了某个元素只出现一次以外，其余每个元素均出现两次。

题目限制

要求最优解

时间复杂度O(N)

空间复杂度O(1)

思路分析

1. 理解题目特点与目标

题目给定条件：我们拿到的是一个非空的整数数组 nums，并且明确知道其中大部分元素都是成对出现的，只有一个元素是单独出现一次，我们的任务就是把这个与众不同、只出现一次的元素找出来。
限制要求：需要设计出时间复杂度为线性（也就是，随着数组元素个数 N 的增加，运行时间按线性增长）的算法，同时只使用常量的额外空间（空间复杂度为，意味着不管输入数组规模多大，额外占用的空间基本固定不变），这就促使我们去寻找一种高效且空间节省的解决办法。

2. 聚焦异或运算特性

核心特性回顾：异或运算（^）有两个关键特性对解题至关重要。其一，对于任意整数 a，a ^ a = 0，意思就是相同的两个数进行异或运算，结果会是 0；其二，0 ^ a = a，也就是 0 和任何数做异或运算，结果就是那个数本身。这两个特性组合起来，为我们解决这个问题提供了巧妙的思路。
结合题目分析：在给定的数组中，那些成对出现的元素，正好可以利用 a ^ a = 0 这个特性。比如数组里有两个 5，当它们进行异或运算时，就会相互抵消变为 0。以此类推，所有成对出现的元素经过异或操作后，最终都会变成 0，而那个只出现一次的元素，由于没有与之相同的元素来和它进行异或抵消，就会在一系列的异或运算后被保留下来。

3. 算法流程设想

初始化阶段：我们需要一个变量来存储异或运算过程中的中间结果以及最终要找的那个只出现一次的元素，将这个变量初始化为 0 是很合理的选择，因为根据 0 ^ a = a 的特性，初始为 0 不会影响后续的异或运算，且方便我们逐步累积运算结果。
遍历与异或运算阶段：通过循环遍历整个整数数组 nums，依次取出数组中的每一个元素，并将这个元素和之前累积的异或结果（最开始是初始化为 0 的那个值）进行异或运算。随着循环的进行，成对出现的元素不断相互抵消变为 0，只留下那个只出现一次的元素参与到最终的异或结果中。
获取结果阶段：当遍历完整个数组后，此时存储异或运算结果的变量中所存放的值，就是我们苦苦寻找的那个只出现一次的元素了，直接返回这个值即可完成任务。

例如，给定数组 [2, 3, 2, 4, 4]：

首先初始化一个变量，设为 result = 0。
开始遍历数组：
- 第一次取出元素 2，执行 result ^= 2，此时 result 变为 2（因为 0 ^ 2 = 2）。
- 第二次取出元素 3，执行 result ^= 3，按照异或运算规则，2 ^ 3 = 1，result 变为 1。
- 第三次取出元素 2，执行 result ^= 2，1 ^ 2 = 3，result 变为 3。
- 第四次取出元素 4，执行 result ^= 4，3 ^ 4 = 7，result 变为 7。
- 第五次取出元素 4，执行 result ^= 4，7 ^ 4 = 3，最终 result 的值为 3，也就是数组中只出现一次的那个元素。

通过这样利用异或运算特性的思路以及对应的算法流程，我们就能高效地满足题目要求，在线性时间复杂度和常量空间复杂度的条件下，准确找出数组中唯一出现一次的元素啦。

具体代码

class Solution {
public:int singleNumber(vector<int>& nums) {int res=0;for(int i:nums){res^=i;}return res;}
};

在上述代码中，首先定义了一个 Solution 类，类中包含了 singleNumber 函数。在 singleNumber 函数里，先将 res 初始化为 0，然后通过基于范围的 for 循环遍历输入的整数数组 nums。在循环体中，使用 res ^= i 对每个元素 i 与当前的 res 进行异或运算。循环结束后，res 中存储的就是数组中唯一出现一次的元素，最后将其返回。

让我们通过一个具体的示例来模拟代码的执行过程，比如数组 [4, 1, 2, 1, 2]。

初始化 res = 0。
第一次循环，i = 4，res ^= 4，此时 res 变为 4（因为 0 ^ 4 = 4）。
第二次循环，i = 1，res ^= 1，根据异或运算规则，4 ^ 1 = 5，res 变为 5。
第三次循环，i = 2，res ^= 2，5 ^ 2 = 7，res 变为 7。
第四次循环，i = 1，res ^= 1，7 ^ 1 = 6，res 变为 6。
第五次循环，i = 2，res ^= 2，6 ^ 2 = 4，所以最终 res 的值就是 4，也就是数组中只出现一次的那个元素。

从时间复杂度来看，代码只需要遍历一次数组，数组长度为 n，所以时间复杂度是，满足线性时间复杂度的要求。在空间复杂度方面，仅使用了一个额外的变量 res 来存储异或运算的结果，不随输入数组规模的增大而增加额外的空间占用，所以空间复杂度是，也符合题目只使用常量额外空间的条件。

综上所述，通过巧妙地运用异或运算的特性，我们能够高效且简洁地解决这一数组元素查找问题，为我们的编程之旅增添一抹亮色。希望大家在遇到类似问题时，能够灵活运用位运算知识，轻松攻克难题。