问
如何对O(n)中给定范围的列表进行排序
快乐伴随su1 发布于 2023-02-13 16:31如果我有一个大小为n的列表,我知道列表中的数字将介于1和2n之间,我将如何解决它,最坏的情况是O(n)？
我在想,如果它在1和n之间,我可以只取数字并用数字的数值交换它 - 1然后如果有任何重复就不会排序.
我想到了一个类似的方法,列表的数字在1到2n之间,但我似乎无法弄明白.有什么帮助吗？
1 个回答
-
在您的情况下,计数排序可以在 O(n)中运行.看看维基百科的定义
count sort是一种根据小整数键对对象集合进行排序的算法; 也就是说,它是一个整数排序算法.它通过计算具有每个不同键值的对象的数量来操作,并对这些计数使用算术来确定输出序列中每个键值的位置.它的运行时间与项目数量和最大和最小键值之间的差异是线性的,因此它仅适用于键的变化不大于项目数的情况下的直接使用
http://en.wikipedia.org/wiki/Counting_sort
2023-02-13 16:34 回答
yushun
撰写答案
今天，你开发时遇到什么问题呢？
立即提问
京公网安备 11010802041100号