1 回答

TA貢獻(xiàn)1818條經(jīng)驗(yàn) 獲得超8個(gè)贊
您的代碼可能可以正常工作,但是:由于需要回溯索引,該算法實(shí)際上只是在天真的暴力冒泡排序算法之上增加了更多的復(fù)雜性。
最簡單的修改就是搜索最小索引 > 比當(dāng)前索引。將位置存儲在字典中.items()作為值的一部分,以便您可以檢索它。但是,你不能對索引進(jìn)行二分查找,因?yàn)樗前粗蹬判虻?,而索引是無序的。這應(yīng)該給你一個(gè)可接受的 O(N) 查找。
最后您仍然必須按索引搜索(優(yōu)先于溫度)。即使使用二進(jìn)制搜索,您嘗試的算法忽略預(yù)排序的 N log N 復(fù)雜性,充其量仍需要 O(N * log N * log N) 進(jìn)行搜索。您當(dāng)前的嘗試實(shí)際上是 O(N^2 log N),但是使用第三個(gè)緩存索引表,最近的索引查找可以變成 log N。
這將是一個(gè)非常復(fù)雜和低效的算法,因?yàn)榛旧媳仨毣厮菽乃阉黜樞?。而且它不會比天真的蠻力有任何優(yōu)勢(客觀上更糟)。
注意:關(guān)鍵是你需要最近的索引,如果你按值排序,它不是排序的順序如果
你仍然想這樣做(我想作為代碼高爾夫挑戰(zhàn)),你會想要添加它的位置索引in .items()of the dict to your dictionary,所以當(dāng)你在字典中查找你的鍵時(shí),你可以通過溫度排序列表找到從哪個(gè)起始位置開始搜索。要獲得日志 N,您需要存儲每個(gè)溫度范圍及其索引范圍。這部分可能實(shí)施起來特別復(fù)雜。當(dāng)然,您需要實(shí)施二進(jìn)制搜索算法。
堆棧算法:
以下算法的基本思想是任何較低的溫度都不再重要。
例如:[...] 10 >20< 9 6 7 21. 20 之后;9 6 7(或任何 <= 20)無關(guān)緊要。9點(diǎn)之后;6和7沒關(guān)系。ETC。
所以從末尾開始迭代,將數(shù)字添加到堆棧,彈出堆棧數(shù)字小于當(dāng)前數(shù)字。
請注意,因?yàn)闇囟鹊臄?shù)量被限制為 70 個(gè)值,并且每次迭代都會將小于當(dāng)前溫度的數(shù)字從堆棧中刪除,因此搜索下一個(gè)溫度的復(fù)雜性和堆棧的大小都被限制為 70 . 換句話說不變。
因此,對于 T 中的每個(gè)項(xiàng)目,在最壞的情況下,您將搜索最多 70 個(gè)值,即:len(T) * 70。因此算法的復(fù)雜度為 O(N):T 中的項(xiàng)目數(shù)。
def dailyTemperatures(T):
res = [0]*len(T)
stack = []
for i, x in reversed([*enumerate(T)]):
if len(stack) < 1:
stack.append((i,x))
else:
while(len(stack)>0 and stack[-1][1]<=x):
stack.pop()
if len(stack)>0 and stack[-1][1]>x:
res[i] = stack[-1][0] - i
print(x, stack)
stack.append((i,x))
return res
print(dailyTemperatures([73, 74, 75, 71, 69, 72, 76, 73]))
添加回答
舉報(bào)