268. 丢失的数字

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

考点

  • 异或技巧

题解

1
2
3
4
5
6
7
8
9
class Solution {
	public:
		int missingNumber(vector<int>& nums) {
			int xorSum = 0;
			for (int i = 0; i <= (int)nums.size(); i++) xorSum ^= i;
			for (auto &num : nums) xorSum ^= num;
			return xorSum;
		}
};

时间复杂度：\(O\left( n \right)\)，其中\(n\)为数组长度

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

思路

假设给定范围为\(a_{0...3}\)，nums的值为\(\left\{ a_0,a_1,a_3 \right\}\)，则需要找到\(a_2\)

根据异或的性质a ^ a = 0与a ^ 0 = a，必有以下恒等式成立： \[ \left( a_0\oplus a_1\oplus a_2\oplus a_3 \right) \oplus \left( a_0\oplus a_1\oplus a_3 \right) =a_2 \] 故而先求出0 ~ nums.size()的异或和，再与nums的元素逐个异或即可得出缺失的元素