力扣加加 - 努力做西湖区最好的算法题解
lucifer 的博客
Github
公众号
搜索文档…
introduction
第一章 - 算法专题
第二章 - 91 天学算法
第三章 - 精选题解
第四章 - 高频考题(简单)
面试题 17.12. BiNode
0001. 两数之和
0020. 有效的括号
0021. 合并两个有序链表
0026. 删除排序数组中的重复项
0053. 最大子序和
0160. 相交链表
0066. 加一
0088. 合并两个有序数组
0101. 对称二叉树
0104. 二叉树的最大深度
0108. 将有序数组转换为二叉搜索树
0121. 买卖股票的最佳时机
0122. 买卖股票的最佳时机 II
0125. 验证回文串
0136. 只出现一次的数字
0155. 最小栈
0167. 两数之和 II 输入有序数组
0169. 多数元素
0172. 阶乘后的零
0190. 颠倒二进制位
0191. 位 1 的个数
0198. 打家劫舍
0203. 移除链表元素
0206. 反转链表
0219. 存在重复元素 II
0226. 翻转二叉树
0232. 用栈实现队列
0263. 丑数
0283. 移动零
0342. 4 的幂
0349. 两个数组的交集
0371. 两整数之和
401. 二进制手表
0437. 路径总和 III
0455. 分发饼干
0504. 七进制数
0575. 分糖果
0665. 非递减数列
0661. 图片平滑器
821. 字符的最短距离
0874. 模拟行走机器人
1128. 等价多米诺骨牌对的数量
1260. 二维网格迁移
1332. 删除回文子序列
第五章 - 高频考题(中等)
第六章 - 高频考题(困难)
后序
由
GitBook
提供支持
0136. 只出现一次的数字
题目地址(136. 只出现一次的数字)
https://leetcode-cn.com/problems/single-number/
题目描述
1
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
2
3
说明:
4
5
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?
6
7
示例 1:
8
9
输入: [2,2,1]
10
输出: 1
11
示例 2:
12
13
输入: [4,1,2,1,2]
14
输出: 4
Copied!
前置知识
位运算
公司
阿里
腾讯
百度
字节
思路
根据题目描述,由于加上了时间复杂度必须是 O(n),并且空间复杂度为 O(1)的条件,因此不能用排序方法,也不能使用 map 数据结构。
我们可以利用二进制异或的性质来完成,将所有数字异或即得到唯一出现的数字。
关键点
1.
异或的性质 两个数字异或的结果
a^b
是将 a 和 b 的二进制每一位进行运算,得出的数字。 运算的逻辑是 如果同一位的数字相同则为 0,不同则为 1
2.
异或的规律
3.
任何数和本身异或则为
0
4.
任何数和 0 异或是
本身
5.
很多人只是记得异或的性质和规律,但是缺乏对其本质的理解,导致很难想到这种解法(我本人也没想到)
6.
bit 运算
代码
语言支持:JS,C,C++,Java,Python
JavaScrip Code:
1
/**
2
* @param {number[]} nums
3
* @return {number}
4
*/
5
var
singleNumber
=
function
(
nums
)
{
6
let
ret
=
0
;
7
for
(
let
index
=
0
;
index
<
nums
.
length
;
index
++
)
{
8
const
element
=
nums
[
index
];
9
ret
=
ret
^
element
;
10
}
11
return
ret
;
12
};
Copied!
C Code:
1
int
singleNumber
(
int
*
nums
,
int
numsSize
){
2
int
res
=
0
;
3
for
(
int
i
=
0
;
i
<
numsSize
;
i
++
)
4
{
5
res
^=
nums
[
i
];
6
}
7
8
return
res
;
9
}
Copied!
C++ Code:
1
class
Solution
{
2
public
:
3
int
singleNumber
(
vector
<
int
>&
nums
)
{
4
auto
ret
=
0
;
5
for
(
auto
i
:
nums
)
ret
^=
i
;
6
return
ret
;
7
}
8
};
9
10
// C++ one-liner
11
class
Solution
{
12
public
:
13
int
singleNumber
(
vector
<
int
>&
nums
)
{
14
return
accumulate
(
nums
.
cbegin
(),
nums
.
cend
(),
0
,
bit_xor
<
int
>
());
15
}
16
};
Copied!
Java Code:
1
class
Solution
{
2
public
int
singleNumber
(
int
[]
nums
)
{
3
int
res
=
0
;
4
for
(
int
n
:
nums
)
5
{
6
// 异或
7
res
^=
n
;
8
}
9
return
res
;
10
}
11
}
Copied!
Python Code:
1
class
Solution
:
2
def
singleNumber
(
self
,
nums
:
List
[
int
])
->
int
:
3
single_number
=
0
4
for
num
in
nums
:
5
single_number
^=
num
6
return
single_number
Copied!
复杂度分析
时间复杂度:$O(N)$
空间复杂度:$O(1)$
延伸
有一个 n 个元素的数组,除了两个数只出现一次外,其余元素都出现两次,让你找出这两个只出现一次的数分别是几,要求时间复杂度为 O(n) 且再开辟的内存空间固定(与 n 无关)。
和上面一样,只是这次不是一个数字,而是两个数字。还是按照上面的思路,我们进行一次全员异或操作, 得到的结果就是那两个只出现一次的不同的数字的异或结果。
我们刚才讲了异或的规律中有一个
任何数和本身异或则为0
, 因此我们的思路是能不能将这两个不同的数字分成两组 A 和 B。 分组需要满足两个条件.
1.
两个独特的的数字分成不同组
2.
相同的数字分成相同组
这样每一组的数据进行异或即可得到那两个数字。
问题的关键点是我们怎么进行分组呢?
由于异或的性质是,同一位相同则为 0,不同则为 1. 我们将所有数字异或的结果一定不是 0,也就是说至少有一位是 1.
我们随便取一个, 分组的依据就来了, 就是你取的那一位是 0 分成 1 组,那一位是 1 的分成一组。 这样肯定能保证
2. 相同的数字分成相同组
, 不同的数字会被分成不同组么。 很明显当然可以, 因此我们选择是 1,也就是 说
两个独特的的数字
在那一位一定是不同的,因此两个独特元素一定会被分成不同组。
Done!
更多题解可以访问我的 LeetCode 题解仓库:
https://github.com/azl397985856/leetcode
。 目前已经 37K star 啦。
关注公众号力扣加加,努力用清晰直白的语言还原解题思路,并且有大量图解,手把手教你识别套路,高效刷题。
以前
0125. 验证回文串
下一个
0155. 最小栈
最近更新
1yr ago
复制链接
内容
题目地址(136. 只出现一次的数字)
题目描述
前置知识
公司
思路
关键点
代码
延伸