Javaでソートされていない整数の配列に一度だけ現れる整数を見つける

Question

私は、各整数が正確に2回現れる未整列の整数配列が与えられている。 Javaで1回だけ表示される整数を見つけるプログラムを記述したいと思います。ここで

は私の試みです：

int findIntegerThatOccursOnce(int[] arr) 
{ 
    HashSet<Integer> hashSet = new HashSet<Integer>(); 
    int mSum = 0; 
    for(int i = 0; i < arr.length; i++) 
    { 
     if(hashSet.contains(arr[i])) 
     { 
      mSum = mSum - arr[i]; 
     } 
     else 
     { 
      hashSet.add(arr[i]); 
      mSum = mSum + arr[i]; 
     } 
    } 
    return mSum; 
} 

私の教授は、それは良い試みだったが、より少ないスペースを使用していますが、私は、私はより少ないスペースでそれを行うことができますどのように見ることができない、より良い1があると言いましたか？スペースの問題について誰でも説明できますか？

Answer 1

あなたの試みは、O（n）の時間とO（n）のスペースを取り、時間と空間の両方に「より悪い」ですシンプルな些細な解決策がたくさんあるとして、実際にはかなり良いです。

Exclusive or (XOR)を配列のすべての整数に使用すると、スペースを取る可能性のある解決策が1つあります。 2回発生するすべての整数がキャンセルされるためです。

これにより、1回だけ表示される1つの整数が残ります。この解決方法は、O（1）スペースを使用します。

Answer 2

すべての数値が1つの値に対して（を除く）を2回表記すると仮定すると、すべての値をxorして結果を返すことができます。これは、コードを作業し、コードレビューを求めているので、同様に、

static int findIntegerThatOccursOnce(int[] arr) { 
    int v = 0; 
    for (int i : arr) { 
     v ^= i; 
    } 
    return v; 
}