如何从无序列表(例如100个元素)中找到前N(如10)个元素的最佳解决方案?
我想到的解决方案是:1. 使用快速排序算法对列表进行排序,2. 获取前10项。
但是否有更好的替代方案呢?
如何从无序列表(例如100个元素)中找到前N(如10)个元素的最佳解决方案?
我想到的解决方案是:1. 使用快速排序算法对列表进行排序,2. 获取前10项。
但是否有更好的替代方案呢?
最佳算法很大程度上取决于K的大小。 如果K很小,那么只需按照BubbleSort算法并迭代外部循环K次即可得到前K个值。 复杂度将为O(n*k)。
然而,对于接近n的K值,复杂度将接近O(n^2)。在这种情况下,快速排序可能是一个不错的选择。
是的,有一种方法可以比快速排序更好。正如Yin Zhu所指出的那样,您可以先搜索第k大的元素,然后使用该元素值作为您的枢轴来分割数组。
在数组中查找前N个元素
可以通过以下技术解决
假设数组长度为m
使用2个循环,类似于冒泡排序 - O(m^2) 2个循环
找到第N个位置的枢轴(快速排序) - 找到第n个位置的枢轴,但最坏情况下的复杂度是O(MLogM),可能会导致O(M^2)
堆 - 堆是非常有用的数据结构,用于这种要求,如getKthMax、getKthMin、getTopN、getBottomN等。 堆可以是最大堆或最小堆,根据要求可以使用其中之一。
在当前情况下,MinHeap更有意义,因为最小值将始终位于顶部,以下是解决方案的步骤
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;
}