Pythonで解く「Single Number II」：3回出現する要素の中から1回だけの数を見つけるアルゴリズム

問題の概要

空ではない整数型の配列が与えられます。この配列では、ある1つの要素だけが1回出現し、それ以外のすべての要素は3回ずつ出現します。この「たった1回しか現れない要素」を見つけるのが本記事のテーマです。

例えば、配列が [2, 2, 3, 2] の場合、出力は 3 となります。

解法のアプローチ

この問題は、各数値をビット単位に分解して集計することで解決できます。各ビット位置における「1」の出現回数を数え、3で割った余りを取れば、余ったビットがそのまま答えの数値を表します。手順は以下の通りです。

1. 配列内の各要素の絶対値の最大値を求め、max_num として保存する。
2. max_bits = int(log2(max_num)) + 2 を計算し、必要なビット数を決める。
3. サイズが max_bits で全要素が 0 のリスト list1 を作成する。
4. 配列内の各数値に対して、最下位ビットから順に各ビットが立っているかを確認し、立っていれば対応する list1[pos] を1増やして右シフトする。
5. すべてのカウントを mod 3 することで、3回出現した要素の寄与を消去する。
6. 残ったビットを組み合わせて結果の数値を再構築する。
7. 最上位ビットが1の場合は負の数として扱うため、-(2^max_bits - result) に変換する。
8. 結果を返す。

Pythonでの実装例

以下のコードで実際の動作を確認できます。

import math
class Solution(object):
    def singleNumber(self, nums):
        max_num = max(map(abs, nums))
        max_bits = (int)(math.log(max_num,2)) + 2
        list1 = [0 for i in range(max_bits)]
        for no in nums:
            pos = 0
            while (no != 0 and pos < max_bits):
                if (no & 1 != 0):
                    list1[pos] += 1
                no >>= 1
                pos += 1
        for i in range(max_bits):
            list1[i] %= 3
        pos = 0
        result = 0
        for i in range(max_bits):
            if (list1[i] != 0):
                result += (2 ** pos)
            pos += 1
        print (list1, max_bits)
        if (list1[max_bits - 1] == 1):
            result = -(2 ** max_bits - result)
        return (result)
ob = Solution()
print(ob.singleNumber([2,2,3,2]))

入力

[2,2,3,2]

出力

[1, 1, 0] 3
3

計算量について

このアルゴリズムの時間計算量は O(n × b)（n は配列の要素数、b は最大ビット数）、空間計算量は O(b) です。ハッシュマップを使わずにビット演算だけで解けるため、メモリ効率が良い点が特徴です。また、負の数も補数表現に基づいた処理で正しく扱える点にも注目してください。