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) C++程序，用于计算大小为3的倒置数
#include
using namespace std;
  
//返回大小为三的逆序数计数
int getInvCount(int arr[],int n)
{
    int invcount = 0;  // 初始化结果
  
    for (int i=0; iarr[j])
            {
                for (int k=j+1; karr[k])
                        invcount++;
                }
            }
        }
    }
    return invcount;
}
  
//主函数
int main()
{
    int arr[] = {8, 4, 2, 1};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "逆序数计数：" << getInvCount(arr, n);
    return 0;
}

输出：

逆序数计数：4

时间复杂度 该方法的时间复杂度为：O(n^3)

更好的方法：

如果我们将每个元素arr[i]视为大小为3的逆序对的中间元素，查找所有大于a[i]且索引小于i的数字，查找所有小于a[i]且索引大于i的数字。我们将大于a[i]的元素数乘以小于a[i]的元素数，并将其添加到结果中。下面是该思想的实现。

//O(n^2)的C++程序，用于计算大小为3的逆序对计数
#include
using namespace std;

//返回大小为3的逆序对计数
int getInvCount(int arr[], int n)
{
    int invcount = 0;  // 初始化结果

    for (int i=1; i arr[j])
                small++;

        //计算arr[i]左侧所有较大元素的数量
        int great = 0;
        for (int j=i-1; j>=0; j--)
            if (arr[i] < arr[j])
                great++;

        //通过将arr[i]作为三个元素的中间，更新逆序数的计数
        invcount += great*small;
    }

    return invcount;
}

//测试函数
int main()
{
    int arr[] = {8, 4, 2, 1};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "逆序数计数：" << getInvCount(arr, n);
    return 0;
}

输出：

逆序数计数：4

时间复杂度 ：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]的元素数量。