计算排列中“反转"的数量 [英] calculating the number of “inversions” in a permutation

问题描述

设 A 是一个大小为 N 的数组.我们称几个索引 (i,j) 为逆"，如果 i 和 A[i] >A[j]

Let A be an array of size N. we call a couple of indexes (i,j) an "inverse" if i < j and A[i] > A[j]

我需要找到一个算法来接收一个N大小的数组(具有唯一的数字)并返回O(n*log(n)).

I need to find an algorithm that receives an array of size N (with unique numbers) and return the number of inverses in time of O(n*log(n)).

推荐答案

您可以使用合并排序 算法.

在合并算法的循环中，左右两半都是升序排列的，我们想把它们合并成一个单独的排序数组.请注意，右侧的所有元素的索引都高于左侧的元素.

In the merge algorithm's loop, the left and right halves are both sorted ascendingly, and we want to merge them into a single sorted array. Note that all the elements in the right side have higher indexes than those in the left side.

假设 array[leftIndex] > array[rightIndex].这意味着在索引为 leftIndex 的元素之后左侧的所有元素也比右侧的当前元素大(因为左侧是升序排列的).因此右侧的当前元素生成 numberOfElementsInTheLeftSide - leftIndex + 1 反转，因此将其添加到您的全局反转计数中.

Assume array[leftIndex] > array[rightIndex]. This means that all elements in the left part following the element with index leftIndex are also larger than the current one in the right side (because the left side is sorted ascendingly). So the current element in the right side generates numberOfElementsInTheLeftSide - leftIndex + 1 inversions, so add this to your global inversion count.

一旦算法完成执行，你就有了答案，在最坏的情况下，归并排序是O(n log n).

Once the algorithm finishes executing you have your answer, and merge sort is O(n log n) in the worst case.

这篇关于计算排列中“反转"的数量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！