Medium

题目描述

给你一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。

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

示例 1：

输入：nums = [1,2,1,3,2,5]
输出：[3,5]
解释：[5, 3] 也是有效的答案。

示例 2：

输入：nums = [-1,0]
输出：[-1,0]

示例 3：

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

提示：

  • 2 <= nums.length <= 3 * 10^4
  • -2^31 <= nums[i] <= 2^31 - 1
  • 除两个数字外，其他数字都出现两次

解题思路

这是一道经典的位运算题目，需要在常量空间内找到两个只出现一次的数字。

核心思路：

  1. 首先对所有数字进行异或运算，由于相同数字异或为0，结果就是两个目标数字的异或值
  2. 这个异或值的某一位为1，说明两个目标数字在该位上不同
  3. 利用这个差异位，将数组分为两组：该位为0的一组，该位为1的一组
  4. 每组分别进行异或运算，就能得到两个目标数字

具体步骤：

  • 第一次遍历：计算所有数字的异或值 xor
  • 找到 xor 中最低位的1（用 xor & -xor 获取）
  • 第二次遍历：根据这个位将数字分组并异或，得到两个结果

这种方法巧妙地利用了异或运算的性质和位操作，在O(n)时间和O(1)空间内解决问题。

代码实现

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int xor_all = 0;
        for (int num : nums) {
            xor_all ^= num;
        }
        
        int diff_bit = xor_all & (-xor_all);
        
        int num1 = 0, num2 = 0;
        for (int num : nums) {
            if (num & diff_bit) {
                num1 ^= num;
            } else {
                num2 ^= num;
            }
        }
        
        return {num1, num2};
    }
};

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        xor_all = 0
        for num in nums:
            xor_all ^= num
        
        diff_bit = xor_all & (-xor_all)
        
        num1 = num2 = 0
        for num in nums:
            if num & diff_bit:
                num1 ^= num
            else:
                num2 ^= num
        
        return [num1, num2]

public class Solution {
    public int[] SingleNumber(int[] nums) {
        int xorAll = 0;
        foreach (int num in nums) {
            xorAll ^= num;
        }
        
        int diffBit = xorAll & (-xorAll);
        
        int num1 = 0, num2 = 0;
        foreach (int num in nums) {
            if ((num & diffBit) != 0) {
                num1 ^= num;
            } else {
                num2 ^= num;
            }
        }
        
        return new int[] {num1, num2};
    }
}

var singleNumber = function(nums) {
    let xorAll = 0;
    for (let num of nums) {
        xorAll ^= num;
    }
    
    let diffBit = xorAll & (-xorAll);
    
    let num1 = 0, num2 = 0;
    for (let num of nums) {
        if (num & diffBit) {
            num1 ^= num;
        } else {
            num2 ^= num;
        }
    }
    
    return [num1, num2];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历数组两次，每次O(n)
空间复杂度O(1)仅使用常量级额外空间存储变量

相关题目