python - 如何有效地找到 10 个最大的子数组？

Question

我需要在条件为 arr[high] - arr[low] < delta 的数组中找到 10 个最大的子数组(最大长度) .现在需要 50 秒(使用 Python)。我可以通过修改算法找到最大子数组以找到最大子数组 sum < somevalue .现在，我只是使用 for 循环并删除每次迭代后找到的最大子数组。我尝试了很多东西，但现在又回到了这里，因为没有任何东西能正常工作。数组已排序。

with open(in_file) as f_in, open(out_file, 'w') as f_out:
    dct = {}        
    mainlst = []
    # Read a file and store values in mainlst and map to some strings using dct

    for i in range(10): 
        start = 0
        end = 0
        maxim = 0
        diff = 0
        current = 1
        max_start = 0
        max_end = 0
        while end < len(mainlst)-1:
            end += 1
            diff = mainlst[end] - mainlst[start]                
            current += 1
            while diff > delta:
                start += 1
                diff = mainlst[end] - mainlst[start]
                current -= 1
            if maxim < current:
                maxim = current
                max_start = start
                max_end = end

        print("".join([dct[mainlst[max_start]], ",", str(maxim)]), file=f_out)

        del mainlst[max_start:max_end+1]

编辑:我忘了提到另一个条件。子数组不能重叠。

Answer 1

有一个O(N lg N)算法:

1. 遍历每个元素，从小到大，设置当前元素为A[low]，O(N)
2. 二进制搜索满足不等式的 A[high] 的索引，O(lg N)
3. 将长度和 (low, high) 对插入优先级队列或任何保持顺序 O(lg N) 次的数据结构
4. 弹出前 10 个或前 N 个项目，这就是答案

已编辑

感谢@m69，使用两个指针可以实现更好的O(N):

1. 遍历每个元素，从小到大，设置两个指针low和high初始指向第一个元素

2. 将high指针向右移动直到A[high] - A[low] >= delta，插入长度和对>(low, high) 在优先级队列或任何在 O(lg N) 时间内保持顺序的数据结构中。

   对于你的特殊情况，你可以简单地使用一个大小为 10 的数组来存储最长的 10 子数组，然后你可以使用 O(1) 来维护这个数组。

   <
3. 将low指针向右移动，重复步骤2。

请注意，low 始终小于或等于 high，并且两个指针始终仅向右移动，每个指针都遍历列表一次。所以它是O(N)，或者对于使用优先级队列的一般情况是O(N lg N)。