问倒置计数法

EN

我试图在数组中计数反演(如果ai > aj和i

我的问题是，是否有可能使用一种形式的桶技术，以实现O(n)的效率与数据的知识。例如，我已经知道数组是一个1-32的排列，因此最大的元素是32 (这意味着我们可以用桶来完成一些事情)。

我一直在考虑这个问题，并注意到如果我们在一个桶中插入一个元素，那么所有桶在插入时大于它的总和就是它的反转计数。但是，如果我们每次在每个桶中添加元素数，那么我就会失去O(n)效率。任何建议，如何保持一个计数，以取消这一处罚。

请注意，置换可以是任意长度的，但是在执行过程中我们知道置换中元素的数量。因此，"n“的值在执行过程中是已知的，并且置换由从"1”到"n“的元素组成。

排序:可以在O(n)时间复杂度中对此数据集进行排序，因为我们可以创建32个桶，并且我们知道每个桶都有一个元素。因此，对于这个特定的例子，桶排序的效率为O(n + 1) = O(n)。