题目：
给定一个非空整数数组，除其中一个元素外，每个元素都出现了两次，找出那个只出现了一次的元素。
例1：
输入： [2,2,1] 输出： 1例2：
输入： [4,1,2,1,2] 输出： 4
思路：
对数组元素进行依次统计，如果一个元素已经出现了两次，则不再关注，直到找到只出现一次的元素。
#include <stdio.h>
//统计在数组arr中数字k出现的次数，n是数组的大小
int countLetter(int* arr, int n, int k) {
int count = 0;
for (int i=0; i<n; i++) {
if (arr[i] == k) {
count++;
}
}
return count;
}
int singleNumber(int* nums, int numsSize) {
for (int i=0; i<numsSize; i++) {
int count = countLetter(nums, numsSize, nums[i]);
if (count == 1)
return nums[i];
}
return 0;
}
int main()
{
int nums[] = {5, 8, 5, 6, 8, 7, 7};
int number = singleNumber(nums, 7);
printf("The single number is %d.\n", number);
} 结果：
系统虽然接受了这个程序，但是运行时间长达400ms，排名也十分靠后。
很明显是时间上吃了亏。在这个程序中，singleNumber函数中有一个for循环，在这个for循环中调用了countLetter函数，而countLetter函数中也有一个for循环，这样时间复杂度就达到了O(n2)，这样的时间复杂度太高了。
所以要想改进的话就要从时间复杂度来入手了
改进思路：
用异或的性质。
异或有交换性，还有一个很有意思的性质，a^b^b=a，即数a两次异或同一个数b（a=a^b^b）仍然为原值a。又如：a^b^a^c^b^c^d=d。
令k等于数组中任意一个数字，并与剩余元素进行异或运算，最后结果就是那个single number。
#include <stdio.h>
int singleNumber(int* nums, int numsSize) {
int k = nums[0];
for (int i=1; i<numsSize; i++) {
k = (k ^ nums[i]);
}
return k;
}
int main()
{
int nums[] = {5, 6, 5, 6, 8, 7, 7};
int number = singleNumber(nums, 7);
printf("The single number is %d.\n", number);
} 结果：
这次运行时间为4ms，相比400ms效率不知道高到哪里去了，排名自然也非常靠前。
异或还有一些其他有意思的性质，比如可以在不引入临时变量的情况下交换两个变量的值等等。
a=10100001, b=00000110
a=a^b; //a=10100111
b=b^a; //b=10100001
a=a^b; //a=00000110 参考：一起玩算法02
推荐一位干货up主：正月点灯笼
京公网安备 11010502036488号