如何找到数组中的求逆数？ [英] How to find the number of inversions in an array ?
问题描述
可能重复：
计算数组中的反转
这是电话采访问题：查找数组中的反转次数。我猜他们的意思是O（N
This is an phone interview question: "Find the number of inversions in an array". I guess they mean O(Nlog N) solution. I believe it cannot be better than O(Nlog N) since this is the sorting complexity.
类似问题可以总结如下：
- 计算元素移动以对数组进行排序的距离的一半：复制数组并对副本进行排序。对于原始数组
a [i]的每个元素，在排序后的副本（二进制搜索）中找到其位置j，然后将距离相加后的一半减去abs（i-j）/ 2。 -
修改
合并排序：修改merge以计算两个排序数组之间的反转，并运行常规的merge sort修改后的合并。
- Calculate half the distance the elements should be moved to sort the array : copy the array and sort the copy. For each element of the original array
a[i]find it's positionjin the sorted copy (binary search) and sum the halves the distancesabs(i - j)/2. Modify
merge sort: modifymergeto count inversions between two sorted arrays and run regularmerge sortwith that modifiedmerge.
这有意义吗？还有其他（也许更简单）的解决方案吗？电话采访不是很困难吗？
Does it make sense ? Are there other (maybe simpler) solutions ? Isn't it too hard for a phone interview ?
推荐答案
实际上是分治法的一种应用，如果您熟悉它，就可以很快提出解决方案。
It is actually an application of divide-and-conquer algorithm, and if you are familiar with it you can come up with the solution quickly.
[1 3 8 5 7 2以4 6]为例，假设我们将数组排序为[1 3 5 8]和[2 4 6 7]，现在我们需要将两个数组组合起来并获得总的反转数。
Take [1 3 8 5 7 2 4 6] as an example, assume we have sorted array as [1 3 5 8] and [2 4 6 7], and now we need to combine the two arrays and get the number of total inversions.
由于每个子数组中已经存在反转次数，因此我们只需要找出由于数组合并而导致的反转次数。每次插入一个元素，例如，将2个元素插入[1＃3 5 8]中，您就可以知道第一个数组与元素2之间有多少个反转（在此示例中为3对）。然后，您可以将它们加起来以获得合并引起的反转次数。
Since we already have number of inversions in each sub-array, we only need to find out the number of inversions caused by array merging. Each time an element is inserted, for example, 2 inserted into [1 # 3 5 8], you can know how many inversions there are between the first array and the element 2 (3 pairs in this example). Then you can add them up to get the number of inversions caused by merging.
这篇关于如何找到数组中的求逆数？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
