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

Question

我正在解决一个编程问题并卡在最后一块拼图上。

这是问题：https ://leetcode.com/problems/daily-temperatures/

我有一个排序的（值）字典，现在我想对字典进行 log(n) 复杂度搜索。这是我到目前为止编写的代码。

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

        

        

        

循环中的注释部分是我遇到麻烦的地方。我无法在任何地方找到可以搜索排序字典然后按键过滤的答案。

解决此问题的任何提示或新建议也将受到赞赏。

Answer 1

您的代码可能可以正常工作，但是：由于需要回溯索引，该算法实际上只是在天真的暴力冒泡排序算法之上增加了更多的复杂性。最简单的修改就是搜索最小索引 > 比当前索引。将位置存储在字典中.items()作为值的一部分，以便您可以检索它。但是，你不能对索引进行二分查找，因为它是按值排序的，而索引是无序的。这应该给你一个可接受的 O(N) 查找。最后您仍然必须按索引搜索（优先于温度）。即使使用二进制搜索，您尝试的算法忽略预排序的 N log N 复杂性，充其量仍需要 O(N * log N * log N) 进行搜索。您当前的尝试实际上是 O(N^2 log N)，但是使用第三个缓存索引表，最近的索引查找可以变成 log N。这将是一个非常复杂和低效的算法，因为基本上必须回溯您的搜索顺序。而且它不会比天真的蛮力有任何优势（客观上更糟）。注意：关键是你需要最近的索引，如果你按值排序，它不是排序的顺序如果你仍然想这样做（我想作为代码高尔夫挑战），你会想要添加它的位置索引in .items()of the dict to your dictionary，所以当你在字典中查找你的键时，你可以通过温度排序列表找到从哪个起始位置开始搜索。要获得日志 N，您需要存储每个温度范围及其索引范围。这部分可能实施起来特别复杂。当然，您需要实施二进制搜索算法。堆栈算法：以下算法的基本思想是任何较低的温度都不再重要。例如：[...] 10 >20< 9 6 7 21. 20 之后；9 6 7（或任何 <= 20）无关紧要。9点之后；6和7没关系。ETC。所以从末尾开始迭代，将数字添加到堆栈，弹出堆栈数字小于当前数字。请注意，因为温度的数量被限制为 70 个值，并且每次迭代都会将小于当前温度的数字从堆栈中删除，因此搜索下一个温度的复杂性和堆栈的大小都被限制为 70 . 换句话说不变。因此，对于 T 中的每个项目，在最坏的情况下，您将搜索最多 70 个值，即：len(T) * 70。因此算法的复杂度为 O(N)：T 中的项目数。def dailyTemperatures(T):&nbsp; &nbsp; res = [0]*len(T)&nbsp; &nbsp; stack = []&nbsp; &nbsp; for i, x in reversed([*enumerate(T)]):&nbsp; &nbsp; &nbsp; &nbsp; if len(stack) < 1:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; stack.append((i,x))&nbsp; &nbsp; &nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; while(len(stack)>0 and stack[-1][1]<=x):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; stack.pop()&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if len(stack)>0 and stack[-1][1]>x:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; res[i] = stack[-1][0] - i&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; print(x, stack)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; stack.append((i,x))&nbsp; &nbsp; return resprint(dailyTemperatures([73, 74, 75, 71, 69, 72, 76, 73]))