上周我偶然发现了这篇论文,作者在第二页提到:
请注意,这会产生整数边权重的线性运行时间.
第三页上的内容相同:
这产生整数边缘权重的线性运行时间和基于比较的排序的O(m log n).
在第8页:
特别是,使用快速整数排序可能会显着加速GPA.
这是否意味着在特殊情况下存在整数值的O(n)排序算法？或者这是图论的专长？
PS:
可能参考文献[3]可能会有所帮助,因为在第一页上他们说:
[...]图表类已经实现了进一步的改进,例如整数边权重[3],[...]
但是我无法访问任何科学期刊.
问题来自于Codility编程训练,它听起来如下:我们有一个数组(A []),其中n(范围从1到100,000)元素,这些是我们的参数.数组的元素是从-2,147,483,648到2,147,483,647的整数,我们需要找到数组中不存在的最小正整数.当然,这可以在O(n*log n)中轻松完成,方法是将它们全部排序并遍历排序的数组,查找缺少的正数(最后一个操作在我的解决方案中具有O(n)最差的时间复杂度).但根据Codility的说法,这个整体问题可以在O(n)中完成,我看不出有任何办法可以做到这一点.有人可以提供一些技巧让我不被卡住吗？
PS这是一个链接,详细描述了我不允许复制的问题 - https://codility.com/c/intro/demo35UEXH-EAT