Sorry, your browser cannot access this site
This page requires browser support (enable) JavaScript
Learn more >

解法

解法一:暴力

每次遍历一个数与后面的数进行比较,如果相等,则此次遍历break,开始遍历下一个数字。

时间复杂度:o(n^2)

空间复杂度:o(n)

解法二:排序

时间复杂度:o(nlog2n)

空间复杂度:o(1)

解法三:使用hash表统计出现的次数

时间复杂度:o(n)

空间复杂度:o(n)

解法四:使用集合统计出现一次的数字

定义一个新的集合,遍历题中给的数组,第一次出现的数字加入集合,遍历到某个数字时,若已经存在集合中则从集合中移除,最终剩余的便是只出现一次的数字,返回即可

时间复杂度:o(n)

空间复杂度:o(n)

解法五:使用集合(利用集合不可以存储重复元素)

使用集合存储数组中出现的所有数字,并计算数组中的元素之和。由于集合保证元素无重复,因此计算集合中的所有元素之和的两倍,即为每个元素出现两次的情况下的元素之和。由于数组中只有一个元素出现一次,其余元素都出现两次,因此用集合中的元素之和的两倍减去数组中的元素之和,剩下的数就是数组中只出现一次的数字。

时间复杂度:o(n)

空间复杂度:o(n)

解法六:使用异或运算

为什么会想到异或运算,因为题目中给了条件,只有一个数字出现了一次,其他数字出现了两次,联想到了异或的性质:a^b^a = a^a^b = 0^b = b

因为题目中其他数字都出现了两次,所以根据异或的交换律和结合律,两两相同的元素在交换后结合到一起边产生多个0。而剩下的只出现1次的数字再与前面的0异或便得到了自己,也就是只出现一次的数字。举例如下:

一个数组为[1, 3, 4, 3, 6, 1, 6]

首先所有数字进行异或:1 ^ 3 ^ 4 ^ 3 ^ 6 ^ 1 ^ 6 ——(应用交换律以及结合律)—–> (1 ^ 1) ^ (3 ^ 3) ^ (6 ^ 6) ^ 4 ——-> 0 ^ 0 ^ 0 ^ 4 ——-> 4

时间复杂度:o(n)

空间复杂度:o(1)

参考

关于异或的性质:请参考

评论