Python - 使用前缀和计算数组中的局部最小值

Question

我正在尝试解决 Min Avg Two Slice来自 Codility 的问题。

我想出了以下代码:

def solution(S, P, Q):
    weights = {'A': 1, 'C': 2, 'G': 3, 'T': 4}
    retVal = []
    for i in range(0, len(P)): 
        if P[i] == Q[i]: 
            retVal.append(weights[S[P[i]]])
        else: 
            retVal.append(local_min(S, weights, P[i], Q[i]))
    return retVal

minimums = {}
def local_min(S, weights, start, end):
    minVal = weights[S[start]]
    for i in range(start,end+1):
        val = weights[S[i]]
        if val == 1: 
            minimums[i] = 1
            return 1
        if val < minVal: 
            minVal = val
        minimums[i] = minVal
    return minVal

这在正确性方面工作得很好，但是它的时间复杂度为 O(n*m)因为我正在重新计算 local_min每次都不会重复使用任何结果。

我正在尝试使用 prefix_sums这里的算法计算局部最小值或以某种方式使用 minimums 记住计算出的最小值对象并在随后对 local_min 的调用中重用它们.

我遇到的问题是这个 - 假设我们有以下数组:

[1, 13, 2, 8, 20, 5]

我们可以计算一个 smallest values seen up to this point 的数组如下:

对于范围 0, 6它只是:

[1,1,1,1,1,1]

对于 1,6它将是:

[13, 2, 2, 2, 2]

对于 2,6 :

[2, 2, 2, 2]

最后:

[8, 8, 8]和 [20, 5]

我正在努力了解如何采用这种方法来计算 smallest value in a given range并降低我的解决方案的时间复杂度。

编辑:

我提出了以下解决方案，它在正确性和性能方面实现了 100% 的 Codility，并实现了 O(n+m) 的时间复杂度:

def solution(S, P, Q):
    weights = {'A': 1, 'C': 2, 'G': 3, 'T': 4}
    retVal = []
    for i in range(0, len(P)): 
        if P[i] == Q[i]: 
            retVal.append(weights[S[P[i]]])
        else: 
            if 'A' in S[P[i]:Q[i] + 1]: 
                retVal.append(1)
            elif 'C' in S[P[i]:Q[i] + 1]: 
                retVal.append(2)
            elif 'G' in S[P[i]:Q[i] + 1]: 
                retVal.append(3)
            else: 
                retVal.append(4)
    return retVal

虽然我对此仍然有点困惑 - 我的假设是 in操作需要 O(n)其中 n是S的长度所以整体复杂度应该是O(n * m)其中 m是P的长度和 Q - 谁能解释为什么复杂性实际上是 O(n + m)

Answer 1

这个问题的难点在于证明有一个简单的解决方案。

特别是，您可以证明您只需要寻找长度为 2 或 3 的切片。

证明:假设有一个长度 >=4 的切片具有最小可能的平均值。我们可以将它分成两片——一片由前两个元素组成，另一片由其余元素组成。任何一部分的平均值都不能小于整体，因为整体的平均值最小，因此两个部分的平均值必须与整体的相同，所以那些初始的 2 个元素是有效的结果从同一个地方开始。

因此只需遍历起始位置并测试所有长度为 2 或 3 的切片，并记住第一个具有最小平均值的切片。