[1] Given an array of integers, every element appears twice except for one. Find that single one. [2] Given an array of integers, every element appears three times except for one. Find that single one. (better solution is needed) Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
题目中文意思就是说给定一个整数数组，数组中所有元素都出现了两次，只有一个元素只出现了一次，找出这个只出现了一次的元素。
用异或来解决这类问题会非常简单。
代码：
int SingleNumber(int arr[] , int length) { int i , xor; for(xor = 0 , i = 0 ; i < length ; ++i) xor = xor ^ arr[i]; return xor; }
完整代码：
1 #include<iostream> 2 using namespace std; 3 4 int SingleNumber(int arr[] , int length) 5 { 6 int i , xor; 7 for(xor = 0 , i = 0 ; i < length ; ++i) 8 xor = xor ^ arr[i]; 9 10 return xor; 11 } 12 13 int main() 14 { 15 int arr[] = {2 , 1 , 2 , 1 , 3 , 4 , 3}; 16 int length = sizeof(arr)/ sizeof(int); 17 18 cout<<SingleNumber(arr , length)<<endl; 19 20 return 0; 21 22 23 }
