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

原文 标签 python sorting search

我正在解决一个编程问题并坚持最后一 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
        
        
        
循环中的注释部分是我遇到麻烦的地方。我无法在任何地方找到可以搜索排序字典然后按键过滤的答案。
任何解决此问题的提示或新建议也值得赞赏。

最佳答案

您的代码可能可以工作,但是:由于需要回溯索引,该算法实际上只是在天真的蛮力冒泡排序算法之上增加了更多的复杂层。
最简单的修改就是搜索比当前索引最小的索引>。将位置存储在字典的 .items() 中作为值的一部分,以便您可以检索它。但是,您不能对索引进行二进制搜索,因为它是按值排序的,而索引不是按顺序排列的。这应该会给你一个可接受的 O(N) 查找。
最后您仍然必须按索引搜索(优先于温度)。即使使用二进制搜索,您尝试的算法,忽略预排序的 N log N 复杂性,充其量仍需要 O(N * log N * log N) 进行搜索。您当前的尝试实际上是 O(N^2 log N),但是使用第三个缓存索引表,最近的索引查找可以变成 log N。
由于基本上必须回溯您的搜索顺序,这将是一个非常复杂且效率低下的算法。而且它比天真的蛮力没有优势(客观上更糟)。
注意:关键是你需要最近的索引,如果按值排序,则不是排序顺序
如果您仍然想这样做(我猜是代码高尔夫挑战),您将需要将其位置索引添加到 .items()将字典添加到字典中,因此当您在字典中查找键时,您可以通过温度排序列表找到开始搜索的起始位置。要获取日志 N,您需要存储每个温度范围及其索引范围。这部分实现起来可能会特别复杂。当然,您需要实现二进制搜索算法。

堆栈算法:
以下算法的基本思想是随后的任何较低温度都不再重要。
例如:[...] 10 >20< 9 6 7 21. 20 之后; 9 6 7(或任何 <= 20)无关紧要。 9点后; 6和7无所谓。等等
所以从最后迭代,将数字添加到堆栈中,弹出小于当前数字的堆栈数字。
请注意,因为温度的数量被绑定(bind)到 70 个值,并且在每次迭代中小于当前温度的数字被从堆栈中删除,所以搜索下一个温度的复杂性和堆栈的大小都被绑定(bind)到 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]))

关于python - O(log n) 在已排序的 Python 字典中搜索,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/62617130/

相关文章:

python - 何时以及为何使用 [:] in python

jquery - 使用jQuery对选择字段进行排序

Python 列表排序取决于项目是否在另一个列表中

java - 使用 elasticsearch 对文本进行分类

search - 搜索引擎如何识别网站上的搜索框?

python - 如何迭代笛卡尔积,使顶级项首先组合?

python - 在 Python 中抓取 javascript 呈现的网站的 "Script part"

python - BeautifulSoup无法解析YouTube页面

sorting - 从终端对redis输出进行排序以与comm命令一起使用

sql - 返回在全文搜索中找到的短语的周围文本,SQL 2005