136. 只出现一次的数字

发表于 分类于 阅读次数： Waline： 本文字数： 158 阅读时长 ≈ 1 分钟

考点

  • 异或技巧

题解

1
2
3
4
5
6
7
8
9
10
class Solution {
	public:
		int singleNumber(vector<int>& nums) {
			int ans = 0;
			for (int i = 0; i < nums.size(); i++) {
				ans ^= nums[i];
			}
			return ans;
		}
};

时间复杂度：\(O\left( n \right)\)

空间复杂度：\(O\left( 1 \right)\)

思路

异或有以下性质，摘选自百度百科：

  • 归零律

  • 恒等律

  • 交换律

  • 结合律

值相同的数作异或运算为空，那么数组内所有元素的异或运算结果即可得到数组中只出现一次的数字

比如nums为{1,1,2,2,3}，二进制表达为{001,001,010,010,011}

那么001 ^ 001 ^ 010 ^ 010 ^ 011 = 011，即为十进制数字3