第七色在线视频,2021少妇久久久久久久久久,亚洲欧洲精品成人久久av18,亚洲国产精品特色大片观看完整版,孙宇晨将参加特朗普的晚宴

為了賬號安全,請及時(shí)綁定郵箱和手機(jī)立即綁定
已解決430363個(gè)問題,去搜搜看,總會有你想問的

O(log n) 在排序的 python 字典中搜索

O(log n) 在排序的 python 字典中搜索

慕運(yùn)維8079593 2023-02-07 10:42:45
我正在解決一個(gè)編程問題并卡在最后一塊拼圖上。這是問題:https ://leetcode.com/problems/daily-temperatures/我有一個(gè)排序的(值)字典,現(xiàn)在我想對字典進(jìn)行 log(n) 復(fù)雜度搜索。這是我到目前為止編寫的代碼。def dailyTemperatures(self, T):    if len(T) == 0:        return []    if len(T) == 1:        return [0]        R = [None] * len(T)        #create map, populate map    M = {}    for i in range(0, len(T)):        M[i] = T[i]        #sort map by value(temps)    MS = sorted(M.items(), key=lambda x: x[1])        for i in MS:        print(i[0], i[1])        for i in range(0,len(T)):        t = T[i]    #base value for comparison                R[i] = 0        x = 0                # find smallest x for which temp T[x] > T[i]        # Dictionary is sorted for Temps                R[i] = x - i            return R                        循環(huán)中的注釋部分是我遇到麻煩的地方。我無法在任何地方找到可以搜索排序字典然后按鍵過濾的答案。解決此問題的任何提示或新建議也將受到贊賞。
查看完整描述

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]))


查看完整回答
反對 回復(fù) 2023-02-07
  • 1 回答
  • 0 關(guān)注
  • 97 瀏覽
慕課專欄
更多

添加回答

舉報(bào)

0/150
提交
取消
微信客服

購課補(bǔ)貼
聯(lián)系客服咨詢優(yōu)惠詳情

幫助反饋 APP下載

慕課網(wǎng)APP
您的移動學(xué)習(xí)伙伴

公眾號

掃描二維碼
關(guān)注慕課網(wǎng)微信公眾號