python - 列表子列表的优化

Question

问题是从给定列表中找到不包含大于指定上限数字的数字的子列表总数说 right 并且子列表最大数量应该大于 a下界说 left 。假设我的列表是:x=[2, 0, 11, 3, 0] 子列表元素的上限是 10 下限是 1 那么我的子列表可以是 [[2],[2,0],[3],[3,0]] 因为子列表总是连续的。我的脚本运行良好并产生正确的输出，但需要一些优化

def query(sliced,left,right):
    end_index=0
    count=0
    leng=len(sliced)
    for i in range(leng):
        stack=[]
        end_index=i

        while(end_index<leng and sliced[end_index]<=right):

            stack.append(sliced[end_index])
            if max(stack)>=left:
                count+=1
            end_index+=1

    print (count)

origin=[2,0,11,3,0]
left=1
right=10
query(origin,left,right)

输出:4

对于列表来说 x=[2,0,0,1,11,14,3,5] 有效的子列表可以是 [[2],[2, 0],[2,0,0],[2,0,0,1],[0,0,1],[0,1],[1],[3],[5],[3, 5]] 总计 10

Answer 1

蛮力

生成每个可能的子列表并检查给定的条件是否适用于每个子列表。

最坏情况:对于每个元素 e在数组中，left < e < right .时间复杂度:O(n^3)

优化的暴力破解(OP的代码)

对于数组中的每个索引，递增地构建一个有效的临时列表(虽然不是真正需要的)。

最坏情况:对于每个元素 e在数组中，left < e < right .时间复杂度:O(n^2)

更优化的解决方案

如果数组有n元素，则数组中的子列表个数为1 + 2 + 3 + ... + n = (n * (n + 1)) / 2 = O(n^2) .我们可以战略性地使用这个公式。

首先，正如@Tim 提到的，我们可以只考虑不包含任何大于 right 的数字的子列表的总和。通过对大于 right 的数字列表进行分区.这将任务减少到只考虑所有元素小于或等于 right 的子列表。然后总结答案。

接下来，通过围绕大于或等于left的数字对缩减子列表进行分区来拆分缩减子列表(是的，子列表的子列表) .对于这些子列表中的每一个，计算该子列表的子列表的可能子列表的数量(如果子列表的长度为 k * (k + 1) / 2 ，则为 k )。完成所有子列表的子列表后，将它们加在一起(例如将它们存储在 w 中)然后计算该子列表的可能子列表数并减去 w .

然后按总和汇总结果。

最坏情况:对于每个元素 e在数组中，e < left .

时间复杂度:O(n)

我知道这很难理解，所以我包含了工作代码:

def compute(sliced, lo, hi, left):
    num_invalid = 0
    start = 0
    search_for_start = True
    for end in range(lo, hi):
        if search_for_start and sliced[end] < left:
            start = end
            search_for_start = False
        elif not search_for_start and sliced[end] >= left:
            num_invalid += (end - start) * (end - start + 1) // 2
            search_for_start = True
    if not search_for_start:
        num_invalid += (hi - start) * (hi - start + 1) // 2
    return ((hi - lo) * (hi - lo + 1)) // 2 - num_invalid

def query(sliced, left, right):
    ans = 0
    start = 0
    search_for_start = True
    for end in range(len(sliced)):
        if search_for_start and sliced[end] <= right:
            start = end
            search_for_start = False
        elif not search_for_start and sliced[end] > right:
            ans += compute(sliced, start, end, left)
            search_for_start = True
    if not search_for_start:
        ans += compute(sliced, start, len(sliced), left)
    return ans