algorithm - 在长度为 n 的列表中找到 x 个最小的整数

Question

您有一个包含 n 个整数的列表，您希望 x 最小。例如，

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

我会在合理的范围内投票选出独特的运行时间，并为最佳运行时间打上绿色勾号。

我将从 O(n * x) 开始:创建一个长度为 x 的数组。遍历列表 x 次，每次取出下一个最小的整数。

编辑

• 您事先不知道这些数字有多大或多小。
• 你不关心最后的顺序，你只想要最小的 x。
• 这已经在一些解决方案中得到处理，但是假设虽然不能保证列表是唯一的，但您也不会得到退化的列表，例如 [1, 1, 1, 1 , 1] 任一个。

Answer 1

您可以在 O(n) 时间内找到第 k 个最小的元素。 This has been discussed on StackOverflow before .有一些相对简单的随机算法，例如 QuickSelect，在 O(n) 的预期时间内运行，而更复杂的算法在 O(n) 的最坏情况下运行。

给定第 k 个最小的元素，你可以遍历列表以找到所有小于第 k 个最小的元素，你就完成了。 (我假设结果数组不需要排序。)

整体运行时间为 O(n)。