[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 }
微信公众号： 猿人谷
如果您认为阅读这篇博客让您有些收获，不妨点击一下右下角的【推荐】
如果您希望与我交流互动，欢迎关注微信公众号
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接。
