题目链接

题目描述：

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 :

输入: [2,2,1]
输出: 1

解题思路

  两种思路，第一种非常简单，利用哈希表记录数组元素出现频次即可。空间复杂度O(n)，如果想将其降至O(1)呢？
  理解题设，除了某个元素只出现一次以外，其余每个元素均出现两次，这时想到一种位运算——异或。

关于异或：

  • 如果a、b两个值不相同，则异或结果为1。如果a、b两个值相同，异或结果为0(假设a，b只能取0 / 1)
  • a xor a = 0
  • b xor 0 = b
  • 异或运算满足交换律：a xor b xor a = (a xor a) xor b = b xor 0 = b

  所以，我们可以通过对数组进行累加的异或运算，得到最终结果。因为，result = nums[0] ^ nums[1] ^ nums[2] ^ nums[3] ^ ...，异或满足交换律使得相同的两元素先一起进行运算得到0，那么根据题设可知最后会剩下0 ^ nums[i]，那个nums[i]就是唯一一个只有一个的数组元素，即为结果。

哈希表

  1. class Solution {
  2. public:
  3.     int singleNumber(vector<int>& nums) {
  4.         unordered_map<int,int> record;
  5.         for(int i = 0; i < nums.size(); i++){
  6.             record[nums[i]]++;
  7.         }
  9.         for(auto iter = record.begin(); iter != record.end(); iter++){
  10.             if(iter->second == 1){
  11.                 return iter->first;
  12.             }
  13.         }
  15.         throw "wrong input";
  16.     }
  17. };

位运算

  1. class Solution {
  2. public:
  3.     int singleNumber(vector<int>& nums) {
  4.         int result = nums[0];
  5.         for(int i = 1; i < nums.size(); i++)
  6.             result = result ^ nums[i];
  7.         return result;
  8.     }
  9. };

如果有错误或者不严谨的地方，请务必给予指正，十分感谢。