Problem
「找单数」系列题，技巧性较强，需要灵活运用位运算的特性。
Given 2*n + 1 numbers, every numbers occurs twice except one, find it. Example Given [1,2,2,1,3,4,3], return 4 Challenge One-pass, constant extra space
运算规则：0^0=0； 0^1=1； 1^0=1； 1^1=0；
即：参加运算的两个对象，如果两个位为“异”（值不同），则该位结果为1，否则为0。
例如：3^5 = 0000 0011 | 0000 0101 =0000 0110，因此，3^5 = 6
题解
根据题意，共有2*n + 1个数，且有且仅有一个数落单，要找出相应的「单数」。鉴于有空间复杂度的要求，不可能使用另外一个数组来保存每个数出现的次数，考虑到异或运算的特性，可将给定数组的所有数依次异或，最后保留的即为结果。
C++
class Solution { public: /** * @param A: Array of integers. * return: The single number. */ int singleNumber(vector<int> &A) { if (A.empty()) { return -1; } int result = 0; for (vector<int>::iterator iter = A.begin(); iter != A.end(); ++iter) { result = result ^ *iter; } return result; } };
源码分析
- 异常处理(OJ上对于空vector的期望结果为0，但个人认为-1更为合理)
- 初始化返回结果
result为0
原创文章，作者：奋斗，如若转载，请注明出处：https://blog.ytso.com/tech/pnotes/20649.html