LC15-出现一次的数字

2020-10-8

一道很简单的题，但题目要求线性复杂度并且要求不使用额外空间。在leetcode上刷过这道题，但是再刷依然是没想到用异或的方法。

在这里总结一下异或的特点：两个相同的数异或为0，不相同的数异或为1，0与一个非0的数异或结果是那个数。因为除了所求数字以外，每个数字都出现了两次，所以通过两两异或得到的结果就是所求数字。

https://www.nowcoder.com/questionTerminal/0bc646909e474ac5b031ec6836a47768

class Solution { public: /** * * @param A int整型一维数组 * @param n int A数组长度 * @return int整型 */ int singleNumber(int* A, int n) { // write code here int res = 0; for(int i=0;i<n;i++) res ^= A[i]; return res; } };