当数组的长度为n和1 <= m <= n^0.5
我认为你可以使用选择算法来找到第m个最小整数(在http://en.wikipedia.org/wiki/Selection_algorithm中有一个复杂的称为BFPRT的整数，它是O(n))，然后使用它作为枢轴来划分数组以获得前m个最小整数。
但是，是否有一种方法可以使用最小堆等数据结构来做到这一点?我怎么知道它是不是O(n)
可以在线性时间内创建最小堆。然后你只需要移除最小元素m次，每次移除的代价是log(n)。这是O(n) + m*O(log(n))，这是O(n) + O(sqrt(n)*log(n))，这是O(n)
edit我原来说O(n) + O(sqrt(n)*log(n))是O(sqrt(n)*log(n))这是错误的因为O(n)实际上是o(sqrt(n)*log(n))这意味着它不是O(sqrt(n)*log(n))
直接使用基数排序在O(n)时间内对数组进行排序。
Build_Heap(A)方法可以在O(n)时间内从随机数组中创建min_heap或max_heap，如果我们创建min_heap则需要O(1)时间来获取最小元素
所以得到最小元素的总时间是O(n)+ (1)即O(n)