推 Rushia: 哇 大師捏 09/15 13:01
推 Rushia: 這解法真的不錯 09/15 13:20
※ 引述《Rushia (みけねこ的鼻屎)》之銘言：
: 2007. Find Original Array From Doubled Array
: 題目：給定一個陣列，若該陣列可以由某個陣列的所有元素乘2之後組合成，我們
: 說這個陣列是一個 Doubled Array，找出這個陣列是否是 Doubled Array 若存在則
: 返回該陣列變成 Doubled Arraay前的陣列。
: Example:
: [1,3,4] => [1,3,4,2,6,8]
思路：
1.反正先sort 從最小元素的開始刪別人 找不到兩倍的自己就不是doubled array
[1,3,4,2,6,8] -> [1,2,3,4,6,8] ->檢查1*2有沒有在array裡 有就刪掉
2.不想每次都O(n)查 所以把預計要刪的元素存成deque
每次檢查最小的那個能不能刪就好(檢查deque[0])
刪不掉就嘗試去刪別人(deque.append())
這裡可以再判斷如果deque[0]*2比你小就直接失敗 因為沒人能和他配了
3.最後看預計要刪的元素是不是空的
Python Code:
from collections import deque
class Solution:
def findOriginalArray(self, changed: List[int]) -> List[int]:
changed.sort()
doubles = deque()
origin = []
for value in changed:
if doubles and doubles[0]*2 == value:
origin.append(doubles.popleft())
else:
doubles.append(value)
return origin if not doubles else []
--
蛤?
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.251.221.156 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1663217880.A.CCE.html