Easy

题目描述

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

解题思路

这道题有多种解法，但考虑到时间复杂度 O(n) 和空间复杂度 O(1) 的要求，异或运算是最优解。

方法一：异或运算（推荐）

异或运算有以下重要性质：

  • a ^ a = 0（相同数字异或为0）
  • a ^ 0 = a（任何数与0异或为自身）
  • 异或运算满足交换律和结合律

由于数组中除了一个数字出现一次外，其他数字都出现两次，我们可以将所有数字进行异或运算。相同的数字异或后会变成0，最终剩下的就是只出现一次的数字。

方法二：哈希表 使用哈希表统计每个数字的出现次数，然后找到出现次数为1的数字。但这种方法空间复杂度为 O(n)，不满足题目要求。

方法三：数学方法 利用 2 * (所有不同数字的和) - 数组总和 = 目标数字 的性质，但需要额外的集合存储，空间复杂度也不是常量级。

代码实现

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

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        result = 0
        for num in nums:
            result ^= num
        return result

public class Solution {
    public int SingleNumber(int[] nums) {
        int result = 0;
        foreach (int num in nums) {
            result ^= num;
        }
        return result;
    }
}

var singleNumber = function(nums) {
    let result = 0;
    for (let num of nums) {
        result ^= num;
    }
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型异或运算解法哈希表解法
时间复杂度O(n)O(n)
空间复杂度O(1)O(n)

其中 n 为数组长度。异或运算解法满足题目要求的常量空间复杂度，是最优解。

相关题目