题目描述
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素
说明:你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例:
输入: [2,2,1]
输出: 1
输入: [4,1,2,1,2]
输出: 4
^ 按位异或 0 ^ 1 = 1 反之都是0,example 1 ^ 1 = 0
0011 1100
^0000 1101
-----------------
0011 0001
按位异或特点:
- 特点1: 自己^自己 = 0
- 特点2: 自己^0 = 自己
自己^自己 = 0
0011
^0011
-----
0000
自己^0 = 自己
0011
^0000
-----
0011
以[2,2,1]解析
00
10
----
10
10
10
----
00
00
10
----
10
Swift答案示例
func singleNumber(_ nums: [Int]) -> Int {
var res = 0
for num in nums {
res ^= num
}
return res
}
原文: https://leetcode-cn.com/problems/single-number/
进阶:
题目描述(难度中等)
有一个 n 个元素的数组，除了两个数只出现一次外，其余元素都出现两次，让你找出这两个只出现一次的数分别是几，要求时间复杂度为 O(n) 且再开辟的内存空间固定(与 n 无关)。
示例:
输入: [1,2,2,1,3,4]
输出: [3,4]
答案
func twoSingleNumber(_ nums: [Int]) -> [Int] {
// let s = nums.reduce(0,{$0 ^ $1})
let s = nums.reduce(0, ^)
let mask = s & (~(s-1))
var num1 = 0
var num2 = 0
for n in nums {
if n & mask == 0 {
num1 ^= n
}else {
num2 ^= n
}
}
return [num1, num2]
}
解析
首先:在这里把所有元素都异或，那么得到的结果就是那两个只出现一次的元素异或的结果
let s = nums.reduce(0, ^) // 0110 6
位运算
0110 // s=6
-0001 // s-1
------
0101
// ~二进制补码运算符
// 是一元运算符，具有"翻转"位效果，即0变成1，1变成0
~0101
------
1010
// &都是1才是1,否则就是0
0110
&1010
------
0010
拿到了唯一的掩码 0010
let mask = s & (~(s-1))
二进制
// 0001 = 1
// 0010 = 2
// 0011 = 3
// 0100 = 4
// 0101 = 5
以二进制掩码0010为标准，将数组的 n 个元素分成两部分
for n in nums {
// 任何数&0010 == 0 或者 == 1
if n & mask == 0 { // (1, 1, 5)
num1 ^= n
}else {// (2, 2, 3)
num2 ^= n
}
}
共遍历数组两次，时间复杂度为O(n)
