本文共 1055 字，大约阅读时间需要 3 分钟。

Single Number

Total Accepted: 62249 Total Submissions: 137347

Given an array of integers, every element appears twice except for one. Find that single one.

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory? 这个题是LeetCode上面AC率最高的一道题。题目是给定一个序列，所有的数字都出现两次，只有一个数字出现一次，找出来这个数字。 我一开始使用了map储存数字和出现频率，然后遍历map找到value为1的输出key。

class Solution {public:    int singleNumber(int A[], int n) {        map
   
     mp;        for(int i = 0; i < n; ++i)        {            mp[A[i]]++;        }        for(map
    
     ::iterator it = mp.begin(); it != mp.end(); ++it)        {            if(it->second == 1)                return it->first;        }    }};
    
   

但是这个方法时间复杂度是很高的map的实现是红黑树，插入/查找元素的时间复杂度是O(logN)，所以这个算法的时间复杂度应该是O(NLogN)并不是Note里面的O(N)，使用的额外空间也非常多。看到Discuss里面其他人的解法基本上都是使用位运算，利用a ^ a == 0这个特性将所有元素全部异或一遍，剩余的结果就是那个出现次数一的元素。

class Solution {public:    int singleNumber(int A[], int n) {        int result = 0;        for(int i = 0; i < n; ++i)            result ^= A[i];        return result;    }};

转载地址：http://fjezb.baihongyu.com/