计算a [i] < a[j] > a [k]的有效算法，其中i <j <k在数组中

-4

给定具有n个元素的未排序数组，如何计算数组中的出现次数，例如i < j < k和a[i] <a[j]> a[k]时间复杂度为O(n log n)。如果更好的时间复杂性是可能的，请让我知道它。我推出了时间复杂度为O(n^3)的算法，处理大的n值太慢了。计算a [i] < a[j] > a [k]的有效算法，其中i <j <k在数组中

count = 0; // count for number of tuples following above condition 
    for(i = 0;i < n; i++) 
     for(j = i + 1;j < n; j++) 
      for(k = j + 1;k < n; k++) 
       if(a[i] < a[j] && a[j] > a[k]) 
        count++; 

for example we have an array [1, 2, 3, 1]. 
Now such occurrences are in index form(0 - based indexing) 
[0 1 3] 
[0 2 3] 
[1 2 3].

来源

2017-07-18 coderbond007

你的数据是什么样的？元组是什么意思？ – kojow7

数据以整数数组的形式 – coderbond007

你可以给一个小样本数组，你会考虑一个元组是什么？ – kojow7

执行在线算法添加整数为一组和二进制搜索整数的个数比当前整数较小A[j]

在法线方向，并且一旦在反向执行一次，因此，对于每个A[j]您可以存储在j之前/之后的整数< A[j]的数目。

答案是总和的所有j

Set<int> st, reverse_st; 
 
int arr[N], reverse_arr[N]; 
 
int A[N], ans = 0; 
 

 
FOR j = 0 to N-1 
 
    arr[j] = # of element in st < A[j], using binary search // O(lg N) 
 
    Insert A[j] into st // O(lg N) 
 

 
FOR j = N-1 to 0 
 
    reverse_arr[j] = # of element in reverse_st < A[j], using binary search 
 
    Insert A[j] into reverse_st 
 
    
 
FOR i = 0 to N-1 
 
    ans += arr[i] * reverse_arr[i] 
 

 
Output ans

使用你的例子A的产物= [1,2,3,1]

ARR = [0， 1,2,0]，reverse_arr = [0,1,1,0]

ans = 1 * 1 + 2 * 1 = 3

来源

2017-07-18 06:37:05 shole

还有一个人想我想问，为什么我在我的问题上得到了低估。我的问题没有错，我认为是这样。 – coderbond007

我不知道。对我来说，我只是想让你实现这个算法，并告诉我它是否有效，因为我没有时间编写它。 – shole

嗯，我得到了算法。谢谢。 – coderbond007

计算a [i] < a[j] > a [k]的有效算法，其中i <j <k在数组中

回答

相关问题