Single Number

描述

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?

分析

异或，不仅能处理两次的情况，只要出现偶数次，都可以清零。

代码

  1. // Single Number
  2. // 时间复杂度O(n)，空间复杂度O(1)
  3. class Solution {
  4. public:
  5.     int singleNumber(vector<int>& nums) {
  6.         int x = 0;
  7.         for (int i : nums) {
  8.             x ^= i;
  9.         }
  10.         return x;
  11.     }
  12. };

相关题目

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/cpp/bitwise-operations/single-number.html