LeetCode / Single Number

昨夜実家の富山から帰ってきました。
台風さんがフェーン現象を巻き起こしたせいで、北陸は地獄のような気候になってます。
私が兼ねてから主張している国民総打ち水法の制定を真摯に考えるべきかと思います！

ja.wikipedia.org

さて、今日の問題。

https://leetcode.com/problems/single-number/

Given a non-empty 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?

Example 1:
Input: [2,2,1]
Output: 1

Example 2:
Input: [4,1,2,1,2]
Output: 4

空ではないintのlistに対して、1つだけ存在する1度しか登場しない要素を返す問題です。
事実上、NoteのYour algorithm should have a linear runtime complexity. Could you implement it without using extra memory?に対して回答できるかどうかの問題と読み替えて良いと思います。

解答・解説

自力ではextra memoryを使う解法しか思いつかなかったので、まずは2つ示します。

解法1

誰でも思いつく（けどこれじゃ問題の意味がないと気づいて書かない）コードを、一応載せておきます。

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        ans = []
        for n in nums:
            if n in ans:
                ans.remove(n)
            else:
                ans.append(n)
        return ans[0]

解法2

こちらの解法は少し難易度が上がるでしょうか。
まずはsetで集合をとり、重複した要素を排除します。この集合の合計値の２倍と、元のlistの差分が答えになります。

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        return sum(set(nums))*2 - sum(nums)

しかし、set(nums)によって空間計算量がに達するのは変わりません。

解法3

さて、extra memoryを使わない解法ですが、ビット演算子のXOR（排他的論理和）を使います。
XORは、2つの入力のどちらか片方が真でもう片方が偽の時には結果が真となり、両方とも真あるいは両方とも偽の時は偽となる演算のことです。
例えば、以下のように計算されます。

>>> 1 ^ 3
2 # 3は2進数で11、1は2進数で01。これのXORは10で、10進数にすると2

このXORを利用して、以下のような解法が成立します。

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        for i in range(1,len(nums)):
            nums[0] ^= nums[i]
        return nums[0]

これは何をしているかというと、全要素についてXORをとっています。
nums = [2,1,4,5,2,4,1]であれば　2 ^ 1 ^ 4 ^ 5 ^ 2 ^ 4 ^ 1　を計算するわけですが、このとき、

• a = bのとき、 a ^ b = 0
• a ^ b = b ^ a

の性質を利用すると、以下のように計算され、解が得られます。

-> 2 ^ 1 ^ 4 ^ 5 ^ 2 ^ 4 ^ 1
=> 2 ^ 2 ^ 1 ^ 1 ^ 4 ^ 4 ^ 5
=> 0 ^ 0 ^ 0 ^ 5
=> 0 ^ 5
=> 5