56 - I. 数组中数字出现的次数

---

comments: true
difficulty: 中等
edit_url: https://github.com/doocs/leetcode/edit/main/lcof/%E9%9D%A2%E8%AF%95%E9%A2%9856%20-%20I.%20%E6%95%B0%E7%BB%84%E4%B8%AD%E6%95%B0%E5%AD%97%E5%87%BA%E7%8E%B0%E7%9A%84%E6%AC%A1%E6%95%B0/README.md

面试题 56 - I. 数组中数字出现的次数

题目描述

一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

 

示例 1：

输入：nums = [4,1,4,6]
输出：[1,6] 或 [6,1]

示例 2：

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

 

限制：

• 2 <= nums.length <= 10000

 

解法

方法一：位运算

由于数组中除了两个数字之外，其他数字都出现了两次，因此对数组中的所有数字进行异或运算，得到的结果即为两个只出现一次的数字的异或结果。

由于这两个数字不相等，因此异或结果中至少存在一位为 $1$。我们通过 lowbit 运算找到异或结果中最低位的 $1$，并将数组中的所有数字按照该位是否为 $1$ 分为两组，这样两个只出现一次的数字就被分到了不同的组中。

对两个组分别进行异或运算，即可得到两个只出现一次的数字。

时间复杂度 $O(n)$，其中 $n$ 为数组长度。空间复杂度 $O(1)$。

https://www.acwing.com/video/2852/

Python3

# reduce 函数将一个二元函数（即接受两个参数的函数）逐步应用到可迭代对象的项上，从左到右，直到将可迭代对象缩减为一个单一的值。from functools import reduce
class Solution:def singleNumbers(self, nums: List[int]) -> List[int]:xs = reduce(xor, nums) #所有元素的异或结果=两个不相等数的异或结果a&ba = 0lb = xs & -xs  #得到最后一个位为1对应的数: 两个不相等数的异或结果a&b ≠ 0，说明至少有一位为1for x in nums:if x & lb:  #核心1：这样运算 只会剩下 第k位为1的a , 其他次数为2的数异或为0a ^= xb = xs ^ a   #核心2：获得a后，xs^a 会将a对应的位抹零，剩下的位就属于breturn [a, b]

Java

class Solution {public int[] singleNumbers(int[] nums) {int xs = 0;for (int x : nums) {xs ^= x;}int lb = xs & -xs;int a = 0;for (int x : nums) {if ((x & lb) != 0) {a ^= x;}}int b = xs ^ a;return new int[] {a, b};}
}

C++

class Solution {
public:vector<int> singleNumbers(vector<int>& nums) {int xs = 0;for (int& x : nums) {xs ^= x;}int lb = xs & -xs;int a = 0;for (int& x : nums) {if (x & lb) {a ^= x;}}int b = xs ^ a;return {a, b};}
};

Go

func singleNumbers(nums []int) []int {xs := 0for _, x := range nums {xs ^= x}lb := xs & -xsa := 0for _, x := range nums {if x&lb != 0 {a ^= x}}b := xs ^ areturn []int{a, b}
}

TypeScript

function singleNumbers(nums: number[]): number[] {let xs = 0;for (const x of nums) {xs ^= x;}const lb = xs & -xs;let a = 0;for (const x of nums) {if (x & lb) {a ^= x;}}const b = xs ^ a;return [a, b];
}

JavaScript

/*** @param {number[]} nums* @return {number[]}*/
var singleNumbers = function (nums) {let xs = 0;for (const x of nums) {xs ^= x;}const lb = xs & -xs;let a = 0;for (const x of nums) {if (x & lb) {a ^= x;}}const b = xs ^ a;return [a, b];
};

C#

public class Solution {public int[] SingleNumbers(int[] nums) {int xs = 0;foreach(int x in nums) {xs ^= x;}int lb = xs & - xs;int a = 0;foreach(int x in nums) {if ((x & lb) != 0) {a ^= x;}}int b = xs ^ a;return new int[] {a, b};}
}

Swift

class Solution {func singleNumbers(_ nums: [Int]) -> [Int] {var xorSum = 0for num in nums {xorSum ^= num}let lowBit = xorSum & -xorSumvar a = 0for num in nums {if (num & lowBit) != 0 {a ^= num}}let b = xorSum ^ areturn [a, b]}
}