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. public class Solution {
  4.     public int singleNumber(int[] nums) {
  5.         int x = 0;
  6.         for (int i : nums) {
  7.             x ^= i;
  8.         }
  9.         return x;
  10.     }
  11. };

相关题目

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