[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 }