列表迭代优化

Question

我正在尝试创建一个函数来查找给定列表 t 中最长的段，它满足两个条件：

1. 段的最后一个数字必须等于或大于段的第一个数字。

2. 段的最后一个数字和第一个数字之间的差异必须等于或小于给定的整数 x.

我能够创建一段有效的代码，但它太慢了。我想不出一个不使用“嵌套 for 循环”的解决方案。

该算法应该使用最多 10^5 个整数的列表，每个整数随机从 1 <= x <= 10^9.

def find(t: list, x: int):
    n = len(t)
    max_len = 0

    for i in range(n):
        for j in range(i, n):
            if t[j] >= t[i] and t[j] - t[i] <= x:
                max_len = max(max_len, j - i + 1)

    return max_len

if __name__ == "__main__":
    print(find([1, 4, 6], 1)) # 1
    print(find([1, 4, 6], 10)) # 3
    print(find([4, 1, 10, 5, 14], 1)) # 4
    print(find([4, 1, 10, 5, 14], 10)) # 5
    print(find([9, 8, 7, 6, 5, 4, 3, 2, 1], 100)) # 1

Answer 1

您需要一个已排序的容器来有效地查找满足这些条件的给定项目剩下的项目。

解决方法是：

• 将项目插入排序的字典中，如

  {element : index}

• 在插入每个项目之前使用二进制搜索查找

  (element - x)

  ，然后获取该找到的元素指向的索引。您不需要搜索从

  current_element - 0

  到

  current_element-x

  的所有元素，因为可以保证

  current_element-x

  在使用二进制搜索进行搜索时会为您提供最远的元素。

• 然后通过最大化

  current index - found index

  来更新结果。

即使列表中有重复元素，这也应该有效。

复杂度是

O(n log n)

n log n 插入排序字典。

使用

SortedDict

包中的

sortedcontainers

代码如下所示：

注意：它没有经过全面测试。

from sortedcontainers import SortedDict
def find(t: List, x: int):
    d = SortedDict()
    d.update({t[0]:0})
    res = 1
    for i, e in enumerate(t[1:]):
      i = i + 1 #because enumerate still starts from i = 0
      idx = i
      if e-x in d:
        idx = d[e-x]
      else:
        found = d.bisect_left(e-x)
        idx = d.peekitem(found-1)[1] if found > 0 else d.peekitem(found)[1]
      if e >= t[idx] and e - t[idx] <= x:
        res = max(res, i-idx+1)
      if not e in d:
        d.update({e:i})
    return res  

print(find([1, 4, 6], 1)) # 1
print(find([1, 4, 6], 10)) # 3
print(find([4, 1, 10, 5, 14], 1)) # 4
print(find([4, 1, 10, 5, 14], 10)) # 5
print(find([9, 8, 7, 6, 5, 4, 3, 2, 1], 100)) # 1

1
3
4
5
1

Answer 2

我想到的第一个想法是向后迭代

j

：

def find(t: list, x: int):
    n = len(t)
    max_len = 0

    for i in range(n):
        # I am too close to the end of the list
        if n - i < max_len:
            break
        # Start my search from the end of the list
        for j in range(n - 1, i, -1):
            possible_max_len = j - i
            if possible_max_len < max_len:
                break
            # I am too close to i 
            if t[j] >= t[i] and t[j] - t[i] <= x:
                max_len = max(max_len, j - i)

    return max_len + 1

长度为 10^4 的最坏情况在我的机器上花费了 3.5 秒。但是完成长度为 10^5 的最坏情况需要 515 秒。

Answer 3

O(n log n) 解决方案：按升序访问值，将它们视为右端点。将仍然相关的可能左端点保留在单队列中。

from collections import deque

def find(t: list, x: int):
    IV = deque()
    result = 1
    for i, v in sorted(enumerate(t), key=lambda e: e[1]):
        while IV and IV[0][1] < v - x:
            IV.popleft()
        if IV:
            result = max(result, i - IV[0][0] + 1)
        while IV and IV[-1][0] > i:
            IV.pop()
        IV.append((i, v))
    return result

在线尝试！