我正在尝试计算数组中的反转(如果 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)。
最佳答案
根据 http://arxiv.org/pdf/1503.01192.pdf众所周知，您找不到比 O(n log n) 更有效的求逆次数。
关于algorithm - 使用分桶计数反转，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/28923848/