令 A 为大小为 N 的数组.
我们调用几个索引 (i,j)如果 i < j 则为“逆”和 A[i] > A[j]
我需要找到一个算法来接收大小为 N 的数组(具有唯一编号)并返回 O(n*log(n)) 的时间倒数.
最佳答案
您可以使用 merge sort算法。
在合并算法的循环中，左右两半都是升序排列的，我们想把它们合并成一个排序好的数组。请注意，右侧所有元素的索引均高于左侧。
假设 array[leftIndex] > array[rightIndex]。这意味着左侧部分中索引为 leftIndex 的元素之后的所有元素也都大于右侧的当前元素(因为左侧是升序排列的)。因此，右侧的当前元素会生成 numberOfElementsInTheLeftSide - leftIndex + 1 次反转，因此将其添加到全局反转计数中。
一旦算法完成执行，您就有了答案，合并排序在最坏的情况下是O(n log n)。
关于arrays - 计算排列中 “inversions” 的数量，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/6523712/