算法得到k最小号码n个项目数组 [英] Algorithm to find k smallest numbers in array of n items

问题描述

我试图写它可以在O打印k个最小数在正大小的数组（n）时间的算法，但我不能减少时间复杂度为n。我怎样才能做到这一点？

I'm trying to write an algorithm which can print the k smallest numbers in an n-size-array in O(n) time, but I cannot reduce the time complexity to n. How can I do this?

推荐答案

您需要使用选择算法，这是O（n）找第K最小的元素，然后再次遍历数组，并把每个元件，它小于/等于它。
选择算法：<一href="http://en.wikipedia.org/wiki/Selection_algorithm">http://en.wikipedia.org/wiki/Selection_algorithm
你必须要注意，如果您有重复：你需要确保你没有返回多于k个元素（这是可能的，如果如您有1,2，...，K，K，K ，...）

的编辑： 维基，完全算法，并返回一个列表，要求：让阵列 A

you will need to find the k'th smallest element using 'selection algorithm', which is O(n), and then iterate the array again and return each element which is smaller/equals it.
selection algorithm: http://en.wikipedia.org/wiki/Selection_algorithm
you will have to pay attention if you have repeats: you will need to make sure you are not returning more then k elements (it is possible if for instance you have 1,2,...,k,k,k,...)

EDIT :
the full algorithm, and returning a list, as requested: let the array be A

 1. find the k'th element in A using 'selection algorithm', let it be 'z'
 2. initialize an empty list 'L'
 3. initialize counter<-0
 4. for each element in A: 
 4.1. if element < z: 
   4.1.1. counter<-counter + 1 ; L.add(element)
 5. for each element in A:
 5.1. if element == z AND count < k:
   5.1.1. counter<-counter + 1 ; L.add(element)
 6. return L

这里要注意的是，如果你的名单可能有重复的第3次迭代是必需的。如果不能 - 这是不必要的，只是改变的条件在4.1到＆lt; =。
还注意到：L.add被插入一个元素链表并因此是O（1）

note here that a 3rd iteration is required if your list might have duplicates. if it can't - it is needless, just change the condition in 4.1 to <=.
also note: L.add is inserting an element to a linked list and thus is O(1).

这篇关于算法得到k最小号码n个项目数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！