我正在尝试计算数组中的反转（如果 a[i] > a[j] 和 i < j，则两个元素 a[i] 和 a[j] 形成反转）。我知道在 O(n^2) 中使用蛮力和在 O(nlgn) 中使用分而治之很容易解决这些问题。
我的问题是，是否有可能使用某种形式的分桶技术来实现 O(n) 的效率以及有关数据的知识。例如，我已经知道数组是 1-32 的排列，因此最大元素是 32（这意味着我们可以用分桶做一些事情）。
我一直在思考这个问题，注意到如果我们在一个桶中插入一个元素，那么在插入时大于它的所有桶的总和就是它的反转计数。但是如果我们每次都添加每个桶中的元素数量，那么它会导致我失去 O(n) 效率。有关如何保持计数以消除此惩罚的任何建议。
请注意，排列可以是任意长度，但在执行过程中我们知道排列中元素的数量。因此，“n”的值在执行期间是已知的，并且排列由从“1”到“n”的元素组成。
排序：可以以 O(n) 的时间复杂度对该数据集进行排序，因为我们可以创建 32 个桶，并且我们知道每个桶将只有一个元素。因此，对于这个特定示例，O(n + M) 的桶排序的效率为 O(n + 1) = O(n)。