[leetcode] Keep Multiplying Found Values by Two
Keep Multiplying Found Values by Two
リストを並べ替えた後、リストに値がある場合は
InをO(1)として使用するためにsetに設定します.setはハッシュ関数とハッシュテーブルによって作成されるデータ構造であるため,リストのように最初からナビゲーションを開始するわけではない.一番前の値、後ろの値、または探索に要する時間はO(1)である.
Programming Live with Larry コレクション内のinのパフォーマンス
最初に思いついた方法
リストを並べ替えた後、リストに値がある場合は
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を探索し続けたため,時間が短縮された.参考資料
Reference
この問題について([leetcode] Keep Multiplying Found Values by Two), 我々は、より多くの情報をここで見つけました https://velog.io/@hotbreakb/leetcode-Keep-Multiplying-Found-Values-by-Twoテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol