[leetcode]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

于是我一开始这样写也accept了。。就是利用一个hashmap，记录每个数字出现的个数。

public class Solution {
    public int singleNumber(int[] A) {
        Map
  
    map=new HashMap
   
    (); for(int i=0;i
    
      m:map.entrySet()){ if(m.getValue()==1){ return m.getKey(); } } return 0; } }
    
   
  

1. a ^ b = b ^ a
2. a ^ b ^ c = a ^ (b ^ c) = (a ^ b) ^ c;

举个例子：

1^2^3^4^4^3^2的结果是啥呢？

一眼大概开不出来。。

根据上面两个法则，改变一下顺序吧

改成2^2^3^3^4^4^1

现在，结果一目了然了吧~

显然是1呗。

有了上面的例子，这道题就简单多了。。

public class Solution {
    public int singleNumber(int[] A) {
         int result = A[0];       
         for(int i = 1; i < A.length; i++){
             result = result ^ A[i];
         }
         return result;
     }
}