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
1
1。我们通过 lowbit
运算找到异或结果中最低位的
1
1
1,并将数组中的所有数字按照该位是否为
1
1
1 分为两组,这样两个只出现一次的数字就被分到了不同的组中。
对两个组分别进行异或运算,即可得到两个只出现一次的数字。
时间复杂度 O ( n ) O(n) O(n),其中 n n n 为数组长度。空间复杂度 O ( 1 ) O(1) 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&b
a = 0
lb = xs & -xs #得到最后一个位为1对应的数: 两个不相等数的异或结果a&b ≠ 0,说明至少有一位为1
for x in nums:
if x & lb: #核心1:这样运算 只会剩下 第k位为1的a , 其他次数为2的数异或为0
a ^= x
b = xs ^ a #核心2:获得a后,xs^a 会将a对应的位抹零,剩下的位就属于b
return [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 := 0
for _, x := range nums {
xs ^= x
}
lb := xs & -xs
a := 0
for _, x := range nums {
if x&lb != 0 {
a ^= x
}
}
b := xs ^ a
return []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 = 0
for num in nums {
xorSum ^= num
}
let lowBit = xorSum & -xorSum
var a = 0
for num in nums {
if (num & lowBit) != 0 {
a ^= num
}
}
let b = xorSum ^ a
return [a, b]
}
}