考虑所有连续子数组的数组每个元素的频率

Question

考虑一个数组 A = [5,1,7,2,3]

所有连续子数组 = { [5], [1], [7], [2], [3], [5,1], [1,7], [7,2], [2,3], [ 5,1,7], [1,7,2], [7,2,3], [5,1,7,2], [1,7,2,3], [5,1,7, 2,3]}

将上面集合中的所有数组替换为其中最大元素：

设置将如下所示： { [5], [1], [7], [2], [3], [5], [7], [7], [3], [7], [7] , [7], [7], [7], [7] }

频率信息：[5] -> 2、[1] -> 1、[7] -> 9、[2] -> 1、[3] -> 2

我的目标是找到上述频率信息。

我的方法：

首先列出 (x,y) 对。x是A中的元素，它的索引是y。

列表：[（5,1）、（1,2）、（7,3）、（2,4）、（3,5）]

相对于第一个元素按降序对列表进行排序。现在，

列表：[（7,3）、（5,1）、（3,5）、（2,4）、（1,2）]

算法：

def f( array, first_index, last_index):
       ->select an element from LIST starting from left which
         is not marked as visited and (first_index <= element.second <=   
         last_index)
       ->calculate frequency info of element in tuple as  (element.secondvalue-first_index+1) + (element.secondvalue-first_index+1)*(last_index - element.second_value)
       ->Mark above element as visited
       ->Recursively solve f( array, first_index,element.secondvalue-1 ),f( array,element.secondvalue+1,last_index)    

我们可以轻松设置合适的基本情况。

时间复杂度：O(n*n)

我已经尝试了很多方法来使用上述算法，但无法提高时间复杂度。我该怎么做？任何提示、方法将不胜感激。

Answer 1

我怀疑你的代码在O(n^2). 无论如何，以更有效的方式解决此问题的一种方法是将每个数字映射到左侧/右侧小于给定项目的项目数。例如：

input = [2 , 3 , 1 , 5 , 4 , 8 , 0]
for number n = 5
leftctsmaller(n) = 3
rightctsmaller(n) = 1

该地图需要O(n^2)生成。其余的很简单。给定左侧和右侧的空间，我们可以轻松确定仅包含比 更小的数字的子数组的数量（n除了n它本身）。