给出n个元素的排序的数组，如何计算在阵列中出现的次数，使得i < j < k和a[i] < a[j] > a[k]在O(n log n)时间复杂度。如果可能有更好的时间复杂度，请告诉我。我提出了时间复杂度的算法，O(n^3)处理大的 n 值太慢了。
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].
做一个在线算法，将整数添加到一个集合中，并二进制搜索小于当前整数的整数个数 A[j]
在正常方向上做一次，在反向上做一次，这样对于每个A[j]你可以存储整数 <A[j]在 / 之前 / 之后的数量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]
年 = 1 * 1 + 2 * 1 = 3
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句