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?
1つを除いて各要素が2回現れる整数配列が与えられます.それを探し出す.
説明:あなたのアルゴリズムには線形の時間的複雑さがあるはずです.追加のメモリを使わずに実現できますか?
最も直接的な考え方は,ハッシュテーブルを用いて要素と出現回数を保存することである.でも新しいスペースを使いました.

	public int singleNumber(int[] A) {
		HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
		for(int i=0;i<A.length;i++){
			if(map.get(A[i]) != null)
				map.put(A[i], map.get(A[i])+ 1);
			else
				map.put(A[i], 1);
		}
		for(Map.Entry<Integer,Integer> m : map.entrySet())
			if(m.getValue() == 1)
				return m.getKey();
		return -1;
	}

1つの比較的巧みな方法は、同じ要素が異や演算を経て0になるため、異或を使用することである.

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

例えば、{2,2,4,3,3}が入力され、計算プロセスは次のようになります.
temp = 0 A[0]=2 temp = 2 ------------------ temp = 2 A[1]=2 temp = 0 ------------------ temp = 0 A[2]=4 temp = 4 ------------------ temp = 4 A[3]=3 temp = 7 ------------------ temp = 7 A[4]=3 temp = 4