计算的置换“转位”的数 [英] calculating the number of “inversions” in a permutation

问题描述

设A是大小的数组 N 。 我们所说的几个指标（I，J）的逆如果 I＆LT; Ĵ和 A [1]＆GT; 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 的阵列（唯一的数字），并返回在时间倒数的数量Ø （N *的log（n）） WC

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)) W.C.

我会AP preciate你的帮助。

I will appreciate your help.

推荐答案

您可以使用归并排序算法。

在合并算法的循环中，左，右两半都排序ascendingly，我们希望将它们合并成一个排序的数组。另外，在右侧的所有元素具有比在左侧更高索引

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.

假设阵列[leftIndex]>阵列[rightIndex] 。这意味着，在左侧部分的所有元素在与索引的元素的 leftIndex 也比当前的右侧（因为左侧ascendingly排序）放大。因此，在右侧的当前元素生成的 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屋！