问题描述
给定一个非空整数数组, 除了某个元素只出现一次以外, 其余每个元素均出现两次. 找出那个只出现了一次的元素.
示例
示例 1:
输入: [2,2,1]
输出: 1
示例 2:
输入: [4,1,2,1,2]
输出: 4
答案
本次题目可以采用异或 (^) 来解决.
异或的规则:
- 0 ^ 0 = 0
- 0 ^ 1 = 1
- 1 ^ 0 = 0
- 1 ^ 1 = 0
总结
任何数异或 0 等于该数本身
两个相同的数异或等于 0
通过二进制进行位数相加
代码如下:
- func singleNumber(_ nums: [Int]) -> Int {
- var singleNum = 0
- for num in nums {
- singleNum = singleNum ^ num
- }
- return singleNum
- }
nums = [2,3,4,3,2]的执行结果如下:
第一次循环:
0 ^ 2 = 2
二进制: 0 + 10 = 10
第二次循环:
2 ^ 3 = 1
二进制: 10 + 11 = 1
第三次循环:
1 ^ 4 = 5
二进制: 1 + 100 = 101
第四次循环:
5 ^ 3 = 6
二进制: 101 + 11 = 110
第五次循环:
6 ^ 2 = 4
二进制: 110 + 10 = 100
结语
语言是招式, 算法是内功. 希望我们勤练内功, 早日成就自己的江湖!
来源: https://juejin.im/post/5c3c52ade51d45524c7cd190