LeetCodeを解き始めたので、何を考えていたのか、何がよかったのかなどを書いていく。

ちなみに、言語はPython3でやってます。

問題

136.Single Number

同じ数字のペアが複数組と、単一の数字が1個だけ含まれた配列から、単一の数値のみを抜き出すというもの。

解答①

import collections

class Solution:
	def singleNumber(self, nums: List[int]) -> int:
		a = [k for k, v in collections.Counter(nums).items() if v == 1]
		return a[0]

初回解答はこれ。collections.Counterを使えば数数えられるしなぁ、とPythonの標準ライブラリに頼った実装。 時間計算量はO(n)。

解答②

class Solution:
	def singleNumber(self, nums: List[int]) -> int:
		s1 = set(nums)
		for i in list(s1):
			nums.remove(i)
		s2 = set(nums)
		s3 = s1 - s2
		return list(s3)[0]

あんまり露骨なライブラリに頼らないでおこうと思ってまず考えたのはこれ。 まずはsetで重複を取り除いたユニークな値の集合(s1)を作り、元の配列からユニークな値を取り除いていくと、重複した値のみが残るので、それを集合に変換(s2)して差を取れば、差分が出ると思って書いた。

ただ、removeがリスト内での検索が必要になるため、時間計算量がO(n)になってしまい、forで回してるので、時間計算量がO(n^2)となってしまい微妙な感じ。

解答③

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

ユニークな値を合計して2倍したものから、元の配列の合計値を引けば出てくると思って書いたものがこれ。 例えば、[A, A, B, B, C]だった場合、ユニークな値を合計して2倍したものは2A+2B+2C、元の配列の合計値は2A+2B+Cになるので、引き算したらCが残るという作戦。

思いついた瞬間は楽しかったけれども、このあと記載する良さそうな解答と比較すると空間計算量が大きくなってしまうようで、ちょっと微妙なのかも。

メジャーな解答

class Solution:
	def singleNumber(self, nums: List[int]) -> int:
		ans = 0
		for n in nums:
			ans ^= n
		return ans

思いつけなかったのだけれども、後々調べてみたらXOR演算子を使ったビット演算で出すのがベストっぽかった。

例えば [1, 2, 1, 2, 3]だった場合、 ans = 0 でスタート ans ^= 1 : 0b0 ^ 0b1 → 0b1(=10進数の1)になる ans ^= 2 : 0b1 ^ 0b10 → 0b11(=10進数の3)になる ans ^= 1 : 0b11 ^ 0b1 → 0b10(=10進数の2)になる ans ^= 2 : 0b10 ^ 0b10 → 0b0(=10進数の0)になる ans ^= 3 : 0b0 ^ 0b11 → 0b11(=10進数の3)になる

という形で、同じ数字で2回XOR取ったら2回反転し、1個だけの数値が残るという仕組み。

引き出しの中にビット演算するということ自体がなかったので、勉強になった。