5

我刚刚接受了一个问题的采访，我很好奇答案应该是什么。问题本质上是：

假设您有一个未排序的 n 个整数列表。您如何找到此列表中的 k 个最小值？也就是说，如果你有一个 [10, 11, 24, 12, 13] 的列表并且正在寻找 2 个最小值，你会得到 [10, 11]。

我有一个 O(n*log(k)) 解决方案，这是我最好的，但我很好奇其他人想出了什么。我将通过发布我的解决方案来避免污染人们的大脑，并将在稍后对其进行编辑。

编辑#1：例如，类似的函数：list getMinVals(list &l, int k)

编辑#2：它看起来像是一个选择算法，所以我也会加入我的解决方案；遍历列表，并使用优先级队列来保存最小值。优先级队列的规范是最大值将在优先级队列的顶部结束，因此在将顶部与元素进行比较时，顶部将被弹出，较小的元素将被推送。这假设优先级队列有一个 O(log n) 推送和一个 O(1) 弹出。

4

2 回答 2

6

这是快速选择算法。它基本上是一种快速排序，您只对数组的一部分进行递归。这是一个简单的 Python 实现，是为了简洁和可读性而不是效率而编写的。

def quickSelect(data, nLeast) :
    pivot = data[-1]
    less = [x for x in data if x <= pivot]
    greater = [x for x in data if x > pivot]
    less.append(pivot)

    if len(less) < nLeast :
        return less + quickSelect(greater, nLeast - len(less))
    elif len(less) == nLeast :
        return less
    else :
        return quickSelect(less, nLeast)

这将平均在 O(N) 中运行，因为在每次迭代中，您都希望将 的大小减小data一个乘法常数。结果不会被排序。最坏的情况是 O(N^2)，但这与快速排序的处理方式基本相同，使用诸如中值 3 之类的东西。

于 2009-02-17T21:16:13.927 回答
4

这通常在算法书籍中的选择算法或“线性选择”下。这是 list 中关于 min/max k 值的具体部分。它是 O(nlog(k))。

于 2009-02-17T21:17:52.940 回答