LeetCode No.2

136. Single Number

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

使用言語：PHP
こちらはfor文やif文で試行錯誤したのですがうまくいきませんでした。。。
関数を探したところ
array_searchとarray_count_valuesを組み合わせて解けました！

class Solution {

    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function singleNumber($nums) {
    $result = array_count_values($nums);
    return array_search('1', $result);
    }
}

ただ上記の解き方は、処理速度がかなり遅いらしく、
処理速度が速い他の解答も見つけたのでご参考までに

例１）
class Solution {

    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function singleNumber($nums) {
        return array_flip(array_count_values($nums))[1];
    }
}

例２）
class Solution {

    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function singleNumber($nums) {
        $result=0;
        for($i=0; $i<count($nums);$i++){
            $result ^=$nums[$i];
        }
        return $result;
    }
}

例３）
class Solution {

    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function singleNumber($nums) {
        $a = 0;
        foreach ($nums as $num) {
            $a = $a ^ $num;
        }

        return $a;
        // Time complexity: O(n)
        // Space complexity: O(1)
    }
}

関数とその他

• array_count_values(array $array): array
  • 配列の値の数を数える
  • https://www.php.net/manual/ja/function.array-count-values
• array_search(mixed $needle, array haystack, bool strict = false): int|string|false
  • 指定した値を配列で検索し、見つかった場合に対応する最初のキーを返す
  • https://www.php.net/manual/ja/function.array-search.php
• array_flip(array $array): array
  • 配列のキーと値を反転する
  • https://www.php.net/manual/ja/function.array-flip

*ドルマークを連続で書くと、他の引数が数式として表現されてしまうので、割愛しています。

• ビットとは
  • コンピュータさんの世界における「0か1が入る箱」
  • コンピュータが処理する最小単位
• ビット演算とは
  • ビットに着目して、そのon/offを操作すること
• ^ (^=)
  • サーカムフレックスと呼ばれ、「XOR」の演算子として使うことが多いです。
  • 排他的論理和と日本語で表現される
  • ビット演算（XOR エックスオア）で使う演算子
  • 2つのビットが同じだったら0、違ったら1になるよ
• ビット演算子
  • AND（&）: 2つのビットがともに1の場合に1を返し、それ以外の場合には0を返します。
  • OR（|）: 2つのビットのうち、いずれかが1の場合に1を返し、どちらも0の場合には0を返します。
  • XOR（^）: 2つのビットのうち、一方が1で他方が0の場合に1を返し、どちらも1または0の場合には0を返します。
  • NOT（~）: ビットを反転させます。つまり、0は1に、1は0に変換します。
    *参考
    https://www.sejuku.net/blog/78679

なんでXORを使うやり方で重複している値を取得できるのか分からなかったので理由を書いておきます！

コードで重複しない値を見つけるためには、XOR演算子が持つ特性を利用しています。
XOR演算子は、同じ値同士をXORすると常に0になり、異なる値同士をXORすると1になるため、以下のような性質があります。
X ^ X = 0
X ^ 0 = X

つまり、同じ値を2回XORすると0になるため、重複している値同士のXORは結果に影響を与えません。逆に、異なる値同士のXORは必ず1になるため、重複していない値同士のXORは結果に反映されます。

そのため、このコードでは、配列内のすべての値を順番にXORしていくことで、重複している値は0になり、重複していない値だけが残ります。最終的には、配列内で重複していない値が1つだけ残るため、それが取得されます。

---

2進法から10進法の変換方法をすぐ忘れそうなのでついでにULR貼っておきます
https://medium-company.com/2%E9%80%B2%E6%95%B0/