优化列表的子列表 [英] Optimization of list's sublist

问题描述

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

the problem is to find total number of sub-lists from a given list that doesn't contain numbers greater than a specified upper bound number say right and sub lists max number should be greater than a lower bound say left .Suppose my list is: x=[2, 0, 11, 3, 0] and upper bound for sub-list elements is 10 and lower bound is 1 then my sub-lists can be [[2],[2,0],[3],[3,0]] as sub lists are always continuous .My script runs well and produces correct output but needs some optimization

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)

output: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

for a list say x=[2,0,0,1,11,14,3,5] valid sub-lists can be [[2],[2,0],[2,0,0],[2,0,0,1],[0,0,1],[0,1],[1],[3],[5],[3,5]] total being 10

推荐答案

蛮力

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

Brute force

Generate every possible sub-list and check if the given criteria hold for each sub-list.

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

Worst case scenario: For every element e in the array, left < e < right. Time complexity: O(n^3)

对于数组中的每个索引，以增量方式构建一个有效的临时列表(虽然并不是真正需要的).

For every index in the array, incrementally build a temporary list (not really needed though) which is valid.

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

Worst case scenario: For every element e in the array, left < e < right. Time complexity: O(n^2)

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

If the array has n elements, then the number of sub-lists in the array is 1 + 2 + 3 + ... + n = (n * (n + 1)) / 2 = O(n^2). We can use this formula strategically.

首先，如@Tim所提到的，我们可以通过将列表中大于right的数字分区，来考虑不包含大于right的数字的子列表的总和.这将任务减少为仅考虑所有元素均小于或等于right的子列表，然后对答案求和.

First, as @Tim mentioned, we can just consider the sum of the sub-lists that do not contain any numbers greater than right by partitioning the list about those numbers greater than right. This reduces the task to only considering sub-lists that have all elements less than or equal to right then summing the answers.

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

Next, break apart the reduced sub-list (yes, the sub-list of the sub-list) by partitioning the reduced sub-list about the numbers greater than or equal to left. For each of those sub-lists, compute the number of possible sub-lists of that sub-list of sub-lists (which is k * (k + 1) / 2 if the sub-list has length k). Once that is done for all the the sub-lists of sub-lists, add them together (store them in, say, w) then compute the number of possible sub-lists of that sub-list and subtract w.

然后按总和汇总您的结果.

Then aggregate your results by sum.

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

Worst case scenario: For every element e in the array, e < left.

时间复杂度:O(n)

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

I know this is very difficult to understand, so I have included working code:

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

这篇关于优化列表的子列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！