Single Number

# 問題1

整数配列numsが与えられる．numsは1つのある整数$x$を除いてすべての整数が2個ずつ格納されている．$x$を求めよ．
https://leetcode.com/problems/single-number/

# 答え

xor演算を使う
- 同じ整数同士のxorは0になることを利用する
- a ^ a == 0
numsを全部xorすれば1つしかない要素が残る

1
2
3
4
5
6
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        ans = nums[0]
        for num in nums[1:]:
            ans ^= num
        return ans

# 問題2

整数配列numsが与えられる．numsは2つのある整数$x$，$y$を除いてすべての整数が2個ずつ格納されている．$x$，$y$を求めよ．
https://leetcode.com/problems/single-number-iii/

# 答え1

setを使う
時間計算量$O(n)$
空間計算量$O(n)$

1
2
3
4
5
6
7
8
9
class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        s = set()
        for num in nums:
            if num in s:
                s.remove(num)
                continue
            s.add(num)
        return list(s)

# 答え2

xorを使う
1つ目の問題と同じように考えると，numsの要素全部のxorを取った結果Pはxとyの重ね合わせになっているので分解する必要がある
- xorの特徴から，一方がわかれば良い
Pを2進数表記したときに1になっている桁に注目すると，そこに桁が立つということは，x，yのどっちかにもその位置の桁が立っていたはず（じゃないとxorした結果に残らない）
時間計算量$O(n)$
空間計算量$O(1)$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        xor1, xor2, i = 0, 0, 0
        # 全部のxorを取る
        for num in nums:
            xor1 ^= num

        # 1が立ってる最下位桁を取る（ホントはどこの桁でもいい）
        for d in range(32):
            if xor1 & 1 << d:
                i = d
                break

        for num in nums:
            if num & 1 << i:
                xor2 ^= num

        return [xor1 ^ xor2, xor2]