在一个数组中找出前N个元素

最佳算法很大程度上取决于K的大小。 如果K很小，那么只需按照BubbleSort算法并迭代外部循环K次即可得到前K个值。 复杂度将为O(n*k)。

然而，对于接近n的K值，复杂度将接近O(n^2)。在这种情况下，快速排序可能是一个不错的选择。

是的，有一种方法可以比快速排序更好。正如Yin Zhu所指出的那样，您可以先搜索第k大的元素，然后使用该元素值作为您的枢轴来分割数组。

在数组中查找前N个元素可以通过以下技术解决 假设数组长度为m

1. 使用2个循环，类似于冒泡排序 - O(m^2) 2个循环

2. 找到第N个位置的枢轴(快速排序) - 找到第n个位置的枢轴，但最坏情况下的复杂度是O(MLogM)，可能会导致O(M^2)

3. 堆 - 堆是非常有用的数据结构，用于这种要求，如getKthMax、getKthMin、getTopN、getBottomN等。 堆可以是最大堆或最小堆，根据要求可以使用其中之一。

在当前情况下，MinHeap更有意义，因为最小值将始终位于顶部，以下是解决方案的步骤

• 迭代数组中的元素
• 将元素添加到堆中
• 如果堆大小> n，则从堆中弹出一个元素，因此任何时候堆中最多只有n个元素
• 迭代堆，并收集所有元素到集合中

时间复杂度： m - 数组大小，n 是前 n 个元素 O(MlogN) -- 堆的添加和删除需要 logN 的时间，我们对数组中的所有元素都进行了这样的操作 空间复杂度 O(N)
// Java 示例代码

public List<Integer> getTopNElements(int[] arr, int n){
   List<Integer> topNList = new ArrayList<>();
   if(arr==null || arr.length <1 || n<1) return topNList;
   
   PriorityQueue<Integer> heap = new PriorityQueue<>(); // default MinHeap
   for(int elem: arr){
      heap.offer(elem);
      if(heap.size() >n) heap.poll();
   }

   while(!heap.isEmpty()){
      topNList.add(heap.poll());
   }
   return topNList;
}

希望这能有所帮助。