首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >问答首页 >如何查找数组中的倒数个数?

如何查找数组中的倒数个数?
EN

Stack Overflow用户
提问于 2010-12-29 16:32:53
回答 2查看 29.5K关注 0票数 19

可能重复:

Counting inversions in an array

这是一个phone interview question:“查找数组中的倒数”。我猜他们的意思是O(N_log N)解。我相信它不会比O(N_log N)更好,因为这是排序的复杂性。

similar question的答案可以总结如下:

  1. 计算元素移动距离的一半来对数组进行排序:复制数组并对副本进行排序。对于原始数组a[i]的每个元素,找到它在排序副本中的位置j (二进制搜索),并将距离abs(i - j)/2.

的两部分相加

  1. Modify merge sort:修改merge以计算两个排序数组之间的倒数,并使用修改后的merge运行常规merge sort

这有意义吗?还有其他(也许更简单)的解决方案吗?电话面试是不是太难了?--

EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/4552591

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档