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

Question

我正在解决一个编程问题，但卡在了最后一 block 拼图上。

这是问题: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。

这将是一个非常复杂且低效的算法，因为基本上必须回溯您的搜索顺序。与简单的暴力相比，它没有任何优势(客观上更糟糕)。
注意:关键是你需要最近的索引，如果按值排序，则索引不是排序的
如果您仍然想这样做(我想作为代码高尔夫挑战)，您将需要将其在字典的 .items() 中的位置索引添加到您的字典中，所以当您查看在 dict 中输入 key，您可以通过温度排序列表找到开始搜索的起始位置。要获得 log N，您需要存储每个温度范围及其索引范围。这部分的实现可能会特别复杂。当然，您需要实现二分搜索算法。

---

堆栈算法:
以下算法的基本思想是随后的任何较低温度都不再重要。
例如:[...] 10 >20< 9 6 7 21。20 之后； 9 6 7(或任何 <= 20)并不重要。 9点之后； 6和7没关系。等等

因此从末尾开始迭代，将数字添加到堆栈中，从堆栈中弹出小于当前数字的数字。

请注意，由于温度的数量被限制为 70 个值，并且每次迭代时小于当前温度的数字都会从堆栈中删除，因此搜索下一个温度的复杂性和堆栈的大小均为限制为 70。换句话说，恒定。
因此，对于 T 中的每一项，在最坏的情况下最多将搜索 70 个值，即:len(T) * 70。 因此算法的复杂度为 O(N):T 中的项目数。

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