Mic*_*ael 18 arrays sorting algorithm
可能重复:
计算数组中的反转
这是一个电话采访问题:"查找数组中的反转次数".我猜他们的意思是O(N log N)解决方案.我认为它不能比O(N log N)更好,因为这是排序的复杂性.
类似问题的答案可归纳如下:
a[i]找到它j在排序副本(二进制搜索)中的位置,并将距离的一半加起来abs(i - j)/2.修改merge sort:修改merge以计算两个已排序数组之间的反转,并merge sort使用修改后的数组运行merge.
是否有意义 ？还有其他(可能更简单)的解决方案吗？电话采访难道不是很难吗？
Zel*_*luX 21
它实际上是分而治之算法的应用,如果您熟悉它,您可以快速提出解决方案.
以[1 3 8 5 7 2 4 6]为例,假设我们已将数组排序为[1 3 5 8]和[2 4 6 7],现在我们需要将两个数组合并得到总数倒置.
由于我们已经在每个子数组中有多个反转,我们只需要找出由数组合并引起的反转次数.每次插入一个元素,例如插入[1#3 5 8]时,您就可以知道第一个数组和元素2之间存在多少个反转(本例中为3对).然后你可以添加它们以获得合并引起的反转次数.