LeetCode: First Unique Numberを解く

問題

LeetCode 30-Day LeetCoding Challenge 28日目です。 あと2問で終わりです。

leetcode.com

今回は新出の問題のようです。しかし、Youtubeには驚異の速度で解説ビデオが上がってました。(見てないけど)

解き方

以下の要件を満たすデータ構造を組み合わせればOK

• Uniqueではなく(duplicated)な数字は出ているかでていないかだけ知れれば良い => HashSet
• Uniqueなナンバーは順番がわかるかつUniqueなデータをadd時に検索できる => LinkedHashSet

PythonにLinkedHashSetは無いためOrderedDictを用います。

回答

from collections import OrderedDict

class FirstUnique:
    def __init__(self, nums: List[int]):
        self.duplicated = set()
        self.uniqueList = OrderedDict()
        for n in nums:
            self.add(n)
        
    def showFirstUnique(self) -> int:
        return next(iter(self.uniqueList.items()))[0] if len(self.uniqueList) > 0 else -1
        
    def add(self, value: int) -> None:
        if value in self.duplicated:
            return

        if value in self.uniqueList:
            self.uniqueList.pop(value)
            self.duplicated.add(value)
        else:
            self.uniqueList[value] = True

OrderedDictの一番最初の要素を取るAPIが無いので、無理やりイテレータを使って取得してます。　　 （なぜAPIないんだろう...）

計算量

時間計算量: O(n)(最初のinit時のみ、addとFirstUniqueはO(1))
空間計算量: O(n)

空間計算量をO(1)で出来るやり方はあるんだろうか？