“给定一个数组,除了某个元素只出现一次,其他元素都出现两次,找出那个只出现一次的元素。”
题目链接:
来源:力扣(LeetCode)
链接: 136. 只出现一次的数字 - 力扣(LeetCode)
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
说明:
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?
示例 1:
输入: [2,2,1]
输出: 1
示例 2:
输入: [4,1,2,1,2]
输出: 4
这个题如果使用暴力破解法,每次从数组中取一个数,然后从剩下的数中对比这个数,如果找不到,则这个数就是要找的数,但是时间复杂度是O(n2),不符合题意。
要降低时间复杂度可以使用Hash表,遍历数组得到每个数字出现的次数,更新Hash表
然后遍历Hash,得到只出现一次的数字,但是时间复杂度还是O(n),如何才能将时间复杂度降到O(1)呢?
根据题意可知,某个元素只出现一次外,其他每个元素出现两次,那么就可以使用异或运算。
代码参考:
class Solution {
public int singleNumber(int[] nums) {
int single = 0;
for (int num : nums) {
single ^= num;
}
return single;
}
}
时间复杂度:O(n)
其中n是数组长度,只需要对数组遍历一次。
空间复杂度:O(1)
只需要常量级的变量空间。
对于本道题可以使用异或运算,对于异或运算有三个特性: