C++程序 计算给定数组中大小为3的逆序数
给定大小为n的数组arr[]。如果a[i] > a[j] > a[k]且i < j < k,则三个元素arr[i]、arr[j]和arr[k]组成大小为3的逆序对。找出大小为3的逆序对的总数。
示例:
输入:{8,4,2,1}
输出:4
大小为3的四个逆序对为(8,4,2)、(8,4,1)、(4,2,1)和(8,2,1)。
输入:{9,6,4,5,8}
输出:2
大小为3的两个逆序对为{9,6,4}和{9,6,5}。
我们已经讨论了通过归并排序、自平衡BST和BIT计算大小为2的逆序数。
简单方法: 遍历所有可能的i、j和k值,并检查条件a[i] > a[j] > a[k]和i < j < k。
输出:
时间复杂度 该方法的时间复杂度为:O(n^3)
更好的方法:
如果我们将每个元素arr[i]视为大小为3的逆序对的中间元素,查找所有大于a[i]且索引小于i的数字,查找所有小于a[i]且索引大于i的数字。我们将大于a[i]的元素数乘以小于a[i]的元素数,并将其添加到结果中。 下面是该思想的实现。
输出:
时间复杂度 :O(n^2)的这种方法
二进制索引树方法:
像大小为2的逆序对一样,我们可以使用二进制索引树找到大小为3的逆序对。强烈推荐首先参考下面的文章。
使用BIT计算大小为2的逆序对
这种方法的想法与上述方法类似。我们计算所有元素的较大元素和较小元素的数量,然后将greater[]与smaller[]相乘并将其添加到结果中。
解决方案:
- 要找出一个索引的较小元素数量,我们从n-1迭代到0。对于每个元素a[i],我们计算(a[i]-1)的getSum()函数,这给出了a[i]-1之前的元素数量。
- 要找出一个索引的较大元素数量,我们从0迭代到n-1。对于每个元素a[i],我们通过getSum()计算小于或等于a[i]的数字之和,并从i(因为i是到那一点的总元素数)中减去它,以便我们可以得到大于a[i]的元素数量。