楼主:
Rushia (みけねこ的鼻屎)
2022-11-18 09:53:26136. Single Number
给予一个整数阵列里面的所有数字都出现两次只有一个数字出现一次,找出这个数字。
题目限制时间复杂度要是线性等级且空间复杂度需是常数等级。
思路:
1.最简单的作法应该是用一个set记录所有数字,若当前数字为n且set不存在n就加入n,
否则移除n,最后剩下的数字就是答案,但是因为题目有限制空间复杂度所以不太OK。
2.可以利用位元运算互斥或的特性,因为 a ^ a = 0 且所有数字只会有1或两个,所以
全部互斥或在一起最后会是只有一个的数字。
JavaCode: