blocks|key|284126|text|它实际上是分而治之算法的一个应用，如果你熟悉它，你可以很快找到解决方案。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|284127|以1+3+8+5+7+2+4+6为例，假设我们已经将数组排序为1+3+5+8和2+4+6+7，现在我们需要将这两个数组组合起来，得到总的倒数。|284128|因为我们已经在每个子数组中有了倒数，所以我们只需要找出由数组合并引起的倒数。每次插入一个元素，例如，2插入到1#3+5+8中，您就可以知道第一个数组和元素2(在本例中为3对)之间有多少个反转。然后，您可以将它们相加，以获得合并导致的反转次数。|284129|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|H|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|I|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|J|8|@]|9|@]|A|$]]|$1|F|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|G|$]]

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.

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.

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.

blocks|key|284131|text|您还可以使用类似计数排序的方法，例如，如果数组只包含较小的数字(例如，如果它是一个字符数组)：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|284132|inversions+=+0
let+count+=+array+of+size+array.Length
for+i+=+0+to+array.Length+-+1+do
++++for+j+=+array[i]+%2B+1+to+maxArrayValue+do
++++++++inversions+=+inversions+%2B+count[j]

++++count[array[i]]+=+count[array[i]]+%2B+1|code-block|syntax|javascript|284133|基本上，对每个元素出现的次数进行计数。然后，在每一步i中，ith元素生成的倒数等于i之前大于i的所有元素的总和，您可以使用所保留的计数轻松地计算出该值。|offset|length|style|CODE|284134|这将是O(n*eps)，其中eps是数组中元素的域。|284135|在我看来，这绝对更简单。至于效率，只有在eps很小的情况下才是好的。如果是，那么它应该比其他方法更快，因为没有递归。|284136|entityMap^0|0|0|Q|1|T|1|15|1|1A|1|0|3|8|E|3|0|K|3|0^^$0|@$1|2|3|4|5|6|7|S|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|T|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|U|8|@$I|V|J|W|K|L]|$I|X|J|Y|K|L]|$I|Z|J|10|K|L]|$I|11|J|12|K|L]]|9|@]|A|$]]|$1|M|3|N|5|6|7|13|8|@$I|14|J|15|K|L]|$I|16|J|17|K|L]]|9|@]|A|$]]|$1|O|3|P|5|6|7|18|8|@$I|19|J|1A|K|L]]|9|@]|A|$]]|$1|Q|3|-4|5|6|7|1B|8|@]|9|@]|A|$]]]|R|$]]

You could also use a counting sort-like approach, if the array only contains small numbers for example (like if it's a character array):

<pre><code>inversions = 0
let count = array of size array.Length
for i = 0 to array.Length - 1 do
 for j = array[i] + 1 to maxArrayValue do
 inversions = inversions + count[j]

 count[array[i]] = count[array[i]] + 1
</code></pre>

Basically, keep a count of how many times each element appears. Then at each step <code>i</code>, the number of inversions the <code>i</code>th element generates is equal to the sum of all the elements bigger than <code>i</code> that come before <code>i</code>, which you can easily compute using the count you're keeping.

This will be <code>O(n*eps)</code> where <code>eps</code> is the domain of the elements in your array.

This is definitely simpler in my opinion. As for efficiency, it's only good if <code>eps</code> is small obviously. If it is, then it should be faster than other approaches since there's no recursion.

<blockquote>
Possible Duplicate: 
<a href="https://stackoverflow.com/questions/337664/counting-inversions-in-an-array">Counting inversions in an array</a>
</blockquote>

This is an <a href="http://www.glassdoor.com/Interview/Phone-Interview-i-Find-the-number-of-inversions-in-an-array-describe-and-code-ii-Find-collinear-points-in-a-given-set-QTN_129352.htm" rel="noreferrer">phone interview question</a>: &quot;Find the number of inversions in an array&quot;. I guess they mean O(Nlog N) solution. I believe it cannot be better than O(Nlog N) since this is the sorting complexity.
The answers to a <a href="https://stackoverflow.com/questions/337664/counting-inversions-in-an-array">similar question</a> can be summarized as follows:
<ol>
<li>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 <code>a[i]</code> find it's position <code>j</code> in the sorted copy (binary search) and sum the halves the distances <code>abs(i - j)/2</code>.
</li>
<li>Modify <code>merge sort</code> : modify <code>merge</code> to count inversions between two sorted arrays and run regular <code>merge sort</code> with that modified <code>merge</code>.
Does it make sense ? Are there other (maybe simpler) solutions ? Isn't it too hard for a phone interview ?
</li>
</ol>

How to find the number of inversions in an array ?

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

 可能重复：这是一个：“查找数组中的倒数”。我猜他们的意思是O(N_log N)解。我相信它不会比O(N_log N)更好，因为这是排序的复杂性。的答案可以总结如下：计算元素移动距离的一半来对数组进行排序:复制数组并对副本进行排序。对于原始数组a[i]的每个元素，找到它在排序副本中的位置j (二进制搜索)，并将距离ab...

问如何查找数组中的倒数个数？
EN

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问如何查找数组中的倒数个数？EN

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问如何查找数组中的倒数个数？
EN