优化时间复杂度的相等值的指数差异

Question

我有这个代码,找到列表中相等值的索引之间的最小差异.(它找到相等值之间的最小"距离".)我想优化其时间复杂度.我的代码目前在O(N ^ 2)中运行.

def func(arr):
    length = len(arr)
    res = 0
    for i and j in range(length):
            if arr[i] == arr[j]:
                res = min(res,i-j)
    return res

我该如何优化它？

Answer 1

这是一个具有O(n)时间复杂度的简单解决方案.对于数组中的每个项目,它将存储它找到的第一个索引,然后检索它以计算差异:

def func(arr):
    d = {}
    return max(i - d.setdefault(x, i) for i, x in enumerate(arr))

更新:如果列表中的项目不可清除或可排序,则需要将它们全部相互比较,并且只能在O(n ^ 2)时间内完成.你可以通过启动内循环从改善原有的代码i+1也将摆脱abs.另一个改进是max只召唤一次而不是每次比赛后:

def func(arr):
    gen = (j - i for i in range(len(arr) - 1) for j in range(i + 1, len(arr))
           if arr[i] == arr[j])
    return max(gen, default=0)

请注意,上面只适用于Python 3.x,因为max2.x不支持default参数.

更新:我能够提出的最有效的算法来覆盖不可用/可排序项目的情况是比较所有对的差异,len(arr) - 1如果找不到匹配,则比较对len(arr) - 2等等.如果列表中的所有项都是唯一的,这当然仍然是O(n ^ 2):

def func(arr):
    for i in range(len(arr) - 1, 0, -1):
        for j in range(len(arr) - i):
            if arr[j] == arr[j+i]:
                return i

    return 0