您有n个整数的列表，你想要的X最小。例如，

You have a list of n integers and you want the x smallest. For example,

x_smallest（[1，2，5，4，3，3）应该返回 [1，2，3] 。

我会投了在合理范围内唯一的运行时间，并给绿色的检查，以最佳的运行时间。

I'll vote up unique runtimes within reason and will give the green check to the best runtime.

我将开始与 O（N * X）：创建长x的数组。遍历列表x次，每次拉出下一个最小整数。

I'll start with O(n * x): Create an array of length x. Iterate through the list x times, each time pulling out the next smallest integer.

编辑

您不知道或大或小的这些数字是如何提前。 您不关心最终的订单，你只是想在X最小。 这已经在一些解决方案进行处理，但让我们说，虽然你不能保证一个独特的名单，你是不会得到一个堕落的列表或者如 [1，1， 1，1，1] 或者 You have no idea how big or small these numbers are ahead of time. You don't care about the final order, you just want the x smallest. This is already being handled in some solutions, but let's say that while you aren't guaranteed a unique list, you aren't going to get a degenerate list either such as [1, 1, 1, 1, 1] either.

推荐答案

您可以在O（n）时间的第k个最小元素。 This 的前上计算器已经讨论过。有比较简单的随机算法，如QuickSelect，在惟愿润（n）的预期时间，在O（n）的运行更复杂的算法最坏情况下的时间。

You can find the k-th smallest element in O(n) time. This has been discussed on StackOverflow before. There are relatively simple randomized algorithms, such as QuickSelect, that run in O(n) expected time and more complicated algorithms that run in O(n) worst-case time.

由于你可以做一个传过来的列表中找到不到第k个最小的所有元素的k个最小元素和你做。 （我假定结果数组不需要进行排序。）

Given the k-th smallest element you can make one pass over the list to find all elements less than the k-th smallest and you are done. (I assume that the result array does not need to be sorted.)

总体运行时间为O（n）。

Overall run-time is O(n).