最佳搜索未排序的整数列表中的k个最小值 [英] Optimum search for k minimum values in unsorted list of integers

问题描述

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

I was just interviewed with a question, and I'm curious what the answer ought to be. The problem was, essentially:

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

Say you have an unsorted list of n integers. How do you find the k minimum values in this list? That is, if you have a list of [10, 11, 24, 12, 13] and are looking for the 2 minimum values, you'd get [10, 11].

我有一个O（n * log（k））解决方案，这是我的最佳选择，但我很好奇其他人的想法。我将通过发布我的解决方案来避免污染人们的大脑，并在一段时间内对其进行编辑。

I've got an O(n*log(k)) solution, and that's my best, but I'm curious what other people come up with. I'll refrain from polluting folks brains by posting my solution and will edit it in in a little while.

编辑＃1：例如，一个函数：
list getMinVals（list& l，int k）

EDIT #1: For example, a function like: list getMinVals(list &l, int k)

编辑＃2：看起来这是一个选择算法，所以我也将解决方案;遍历列表，并使用优先级队列保存最小值。优先级队列的规范是最大值将最终出现在优先级队列的顶部，因此在将顶部与某个元素进行比较时，顶部将弹出，较小的元素将被推送。假定优先级队列有一个O（log n）推送和一个O（1）弹出消息。

EDIT #2: It looks like it's a selection algorithm, so I'll toss in my solution as well; iterating over the list, and using a priority queue to save the minimum values. The spec on the priority queue was that the maximum values would end up at the top of the priority queue, so on comparing the top to an element, the top would get popped and the smaller element would get pushed. This assumed the priority queue had an O(log n) push and an O(1) pop.

推荐答案

这是<一种href = http://en.wikipedia.org/wiki/Quick_select rel = nofollow noreferrer> quickSelect 算法。基本上，这是一种快速排序，您只需递归数组的一部分即可。这是一个简单的Python实现，是出于简洁和可读性而不是效率的目的。

This is the quickSelect algorithm. It's basically a quick sort where you only recurse for one part of the array. Here's a simple implementation in Python, written for brevity and readability rather than efficiency.

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。

This will run in O(N) on average, since at each iteration, you are expected to reduce the size of data by a multiplicative constant. The result will not be sorted. The worst case is O(N^2), but this is dealt with in essentially the same way as a quick sort, using things like median-of-3.

这篇关于最佳搜索未排序的整数列表中的k个最小值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！