算法 – 查找长度为n的列表中的x最小整数

你有一个n个整数的列表,你想要x最小.例如,

x_smallest([1,2,5,4,3],3)应返回[1,2,3].

我会在理由之内投票独一无二的运行时间,并将绿色检查运行到最佳运行时间.

我将从O(n * x)开始:创建长度为x的数组.迭代列表x次,每次拉出下一个最小的整数.

编辑

>你不知道这些数字是多大还是小.
>你不在乎最终的顺序,你只想要x最小.
>这已经在一些解决方案中处理了,但是让我们说,虽然你不能保证一个唯一的列表,但是你不会得到诸如[1,1,1,1,1,1]的退化列表.

您可以在O(n)时间内找到第k个最小的元素. This has been discussed on StackOverflow before.在O(n)期望时间内运行的比较简单的随机算法,如QuickSelect,在O(n)最坏情况下运行的算法更复杂.

给定第k个最小元素,您可以通过列表找到所有小于第k个最小值的元素,并完成. (我假设结果数组不需要排序.)

总体运行时间为O(n).

相关文章
相关标签/搜索