前几天，接到电话面试，结果问了一个算法题，说给一些乱序的整数，找出前k个最小整数，当时直接想到的就是先用nlogn的算法比如快速排序进行升序排列，然后取前k个值就行了，但是对方说还有没有更加高效的方法。想了半天没有想起来。挂完电话后我想到虽然使用快速排序可以达到目的，但是却把所有的序列都进行了排序，做了很多无用功。为了去除前k个最小值，我们可以在快速排序的基础上进行剪枝优化，去除一些不必要的排序。模仿快排算法，虽然快排使用分而治之的思想提高了排序效率，但是目标要求的是查找前k个最小值，再这样的背景下，分治却成为了影响性能的因素。因为我们在进行一次划分操作后，中轴的位置（在这里是第几个的意思）如果大于k值的话，中轴后面连同中轴本身都不是此问题的解集的一部分。如果等于k的话查找结束，连同中轴本身就是问题解。如果小于k的话，就可以忽略中轴以后的数据了，没必要在对其进行分解排序了，因为他们肯定不是问题的解。前几天，接到电话面试，结果问了一个算法题，说给一些乱序的整数，找出前k个最小整数，当时直接想到
阅读背景：
电话面试----关于前k个最小数的问题
来源：互联网
分享到：
