LeetCode-138一度しか現れない数字

タイトル
空でない整数配列が与えられ、ある要素が1回しか現れない以外は、各要素が2回現れます.それが一度しか現れなかった要素を見つけます.
説明:
あなたのアルゴリズムは線形時間の複雑さを持つべきです.余分なスペースを使わずに実現できますか?
ぶんせき
1 Javaでのソートを考えて順番を並べた後、最初の位置と中間位置に分けて処理し、最後に最後の位置に戻る
このようなやり方は明らかによくない.Javaのarraysを使ったとは言わない.sortは2回現れない唯一の要素を見つける方法も愚かだ.
2後になってやっとこの問題がビット演算処理であることを知って、私達は知っていて、2つの同じ数字の2進数の取りと操作の結果は0で、だから配列の中のすべての同じ要素は互いに相殺することができて、最後に残ったのはそれが1回現れた数字で、最後に戻ればいいです
Javaで異種またはオペレータが異なるのは1で同じは0です
～逆演算子
&オペレータと
コード#コード#

class Solution {
    public int singleNumber(int[] nums) {
        int result = nums[0];
        for(int i = 1; i < nums.length; i++){
            result^=nums[i];
        }
        return result;
        // Arrays.sort(nums);
        // for (int i = 0; i < nums.length - 1; i++) {
        //     if(i == 0 && nums[i + 1] != nums[i]){
        //         return nums[0];
        //     }else if(i != 0 && nums[i] != nums[i - 1] && nums[i] != nums[i + 1]){
        //         return nums[i];
        //     }
        // }
        // return nums[nums.length - 1];
    }
}

拡張1
配列の中で他の数字はすべて3回現れて、1つだけ1回現れて、この数を求めます
2人は4つの状態00 10 01 11を表します.私たちは3つの状態00-10-01-00がそれぞれ初期状態であり、onesに割り当てられ、twosに割り当てられ、すべてをクリアする必要があります.
ones twos 2 bitビットストレージ
コード#コード#

class Solution {
    public int singleNumber(int[] nums) {
        int ones = 0, twos = 0;
        for(int i = 0; i< nums.length; i++){
            ones = (ones ^ nums[i]) & ~twos;
            twos = (twos ^ nums[i]) & ~ones;
        }
        return ones;
    }
}

time: o(n)
space:o(1)
ビット演算を使わずhashmapで
key格納要素の値、value格納回数
最後にvalueが1の値を見つけます
拡張2
1つの配列は他の2回、2つは1回しか現れなくて、この2つの数を求めます
ぶんせき
1異またはすべての数
2 diffと上diffの符号化形式の逆符号化プラス1
例
    3 011 
    5 101
    3&5 = 110 = diff = 6
    -diff = 1111010
与上結果は10
結論a bが異なるとabのバイナリは1つだけ異なる
    6 & -6 10
では、違うのは最下位から2位だと知りました.
元の配列を2つに1つ、2番目のビットを1つ、0に分けてそれぞれこの2つの配列に対して異和演算を行うと、最終的な結果が得られます.
コード#コード#

public int[] singleNumber(int[] nums) {
        int diff = 0;
        for (int i = 0; i < nums.length; i++) {
            diff ^= nums[i];
        }
        diff &= -diff;
        int res[] = new int[2];
        for (int i = 0; i < nums.length; i++) {
            if((nums[i] & diff) == 0){
                res[0] ^= nums[i];
            }else{
                res[1] ^= nums[i];
            }
        }
        return res;  
    }