2

实际上，我正在自学算法，在这里我试图解决以下问题：

我们有一个任意顺序的n个正整数数组，我们有k，k>=1到n。问题是输出k个最小的奇数。如果 A 中的奇数个数小于 k，我们应该报告所有奇数。例如如果A = [2, 17, 3, 10, 28, 5, 9, 4, 12,13, 7] 并且k = 3，那么输出应该是3, 5, 9。我想解决这个问题在 O(n) 时间内。

我目前的解决方案是有另一个只有奇数的数组，然后我应用这个算法，即通过找到中位数并将列表分成 L、Median、Right 并比较 k 如下：

If |L|<k<= (|L|+|M|) Return the median 
else if K<|L|, solve the problem recursively on (L)
else work on (R, k- (|L|+|M|)

任何帮助表示赞赏。

4

1 回答 1

2

假设输出可以是任何顺序：

创建一个只有奇数的单独数组。

使用选择算法来确定第 k 个项目。一种这样的算法是快速选择（O(n)平均运行），它与快速排序有关 - 它通过一些枢轴对数组进行分区，然后根据每个分区的大小递归地转到分区的一侧。有关更多详细信息，请参阅此问题。

由于 quickselect 对输入进行分区，因此您将能够在运行此算法后直接输出结果（如Karoly所述）。

上述两个步骤都采取O(n)，因此整体运行时间为O(n).

如果您需要按升序输出：

如果 k = n，并且所有数字都是奇数，那么O(n)解决这个问题的方法就是O(n)排序算法，但没有人知道这种算法。

对于任何考虑不同意的人，说一些非基于比较的排序是O(n)- 它不是，这些算法中的每一个在复杂性中都有一些其他因素，例如数字的大小。

对于无界数，您在这里可以做的最好的事情是使用Proger 的答案( O(n + k log n)) 中建议的方法，或者遍历输入，保持最小奇数堆( )。kO(n log k)

于 2013-10-19T12:55:32.327 回答