题目

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?

分析

给定一个序列 找出只出现一次的元素，其它元素均出现2次；

要求线性时间，不需要额外空间。

最先采用的方法是先对序列排序，然后遍历一次即可找到，此时复杂度为O(nlogn)，不过OJ竟然过了。

还是要思考下线性时间的实现方法的，

/*利用异或运算实现，复杂度为O(n) a^b = b^a ; a^a = 0 ; 0^a = a^0 = a*/

由此，对整个序列每个元素采取异或运算，0^a1^a2^…^an最终得到的结果即是那个只出现一次的元素。

这个方法实在是太赞了！可惜不是我想出来的… ^||^

AC代码

class Solution {

public:

    /*利用算法库的排序实现，复杂度为O(nlogn)*/

    //int singleNumber(vector<int>& nums) {

    //  if (nums.empty())

    //      return -1;

    //  sort(nums.begin(), nums.end());

    //

    //  int size = nums.size();

    //  for (int i = 0; i < size - 1; i += 2)

    //  {

    //      if (nums[i] != nums[i + 1])

    //      {

    //          return nums[i];

    //      }//if

    //  }//for

    //  return nums[size - 1];

    //}

    /*利用异或运算实现，复杂度为O(n) a^b = b^a ; a^a = 0 ; 0^a = a^0 = a*/

    int singleNumber(vector<int>& nums) {

        if (nums.empty())

            return -1;

        int ret = 0 , size = nums.size();

        for (int i = 0; i < size; ++i)

            ret = ret ^ nums[i];

        return ret;

    }

};

GitHub测试程序源码