[leetcode] Keep Multiplying Found Values by Two

Keep Multiplying Found Values by Two

最初に思いついた方法

リストを並べ替えた後、リストに値がある場合はoriginal *= 2を行います.そうすればwhile文ではO(N)で解決できますが、「indexをnumsの果てまで行かせる必要はありますか?」という考えが生まれた.

class Solution:
    def findFinalValue(self, nums: List[int], original: int) -> int:
        nums = sorted(nums)
        index = 0
        
        try:
            index = nums.index(original)
        except:
            return original
        
        while index < len(nums):
            if nums[index] == original:
                original *= 2
            index += 1
        
        return original

他人を解く

InをO(1)として使用するためにsetに設定します.setはハッシュ関数とハッシュテーブルによって作成されるデータ構造であるため,リストのように最初からナビゲーションを開始するわけではない.一番前の値、後ろの値、または探索に要する時間はO(1)である.

class Solution:
    def findFinalValue(self, nums: List[int], original: int) -> int:
        numsSet = set(nums)
        
        while original in numsSet:
            original *= 2
        
        return original

従来のコードのようにnumsを探索し続けたため,時間が短縮された.

参考資料

Programming Live with Larry

コレクション内のinのパフォーマンス