我相信有一种方法可以找到长度为n的O(n)无序数组中第k大的元素。也可能是期望O(n)之类的。我们该怎么做呢?
当前回答
创建优先级队列。 将所有元素插入堆中。 调用poll() k次。 getKthLargestElements(int[] arr) { PriorityQueue<Integer> pq = new PriorityQueue<>((x, y) -> (y-x)); //将所有元素插入堆中 For (int ele: arr) pq.offer(避署); //调用poll() k次 int i = 0; 而(i< k) { Int result = pq.poll(); } 返回结果; }
其他回答
A Programmer's Companion to Algorithm Analysis给出了一个O(n)的版本,尽管作者指出常数因子如此之高,您可能更喜欢简单的排序-列表-然后选择方法。
我已经回答了你的问题:)
我实现了在n个未排序元素中寻找第k个最小值的动态规划,特别是竞赛方法。执行时间为O(n + klog(n))。所使用的机制在维基百科关于选择算法的页面上被列为方法之一(如上面的帖子之一所示)。你可以阅读算法,也可以在我的博客页面“查找k个最小值”上找到代码(java)。此外,逻辑可以对列表进行部分排序——在O(klog(n))时间内返回第一个K min(或max)。
虽然代码提供了第k个最小值的结果,但可以使用类似的逻辑来查找O(klog(n))中的第k个最大值,忽略创建比赛树的前期工作。
这种方法怎么样
保持一个长度为k的缓冲区和一个tmp_max,得到tmp_max为O(k)并执行n次因此类似于O(kn)
是这样还是我漏掉了什么?
虽然它没有击败快速选择的平均情况和中值统计方法的最坏情况,但它非常容易理解和实现。
下面是完整实现的链接,其中相当广泛地解释了在无序算法中查找第k个元素的算法是如何工作的。基本思想是像快速排序一样对数组进行分区。但为了避免极端情况(例如每一步都选择最小的元素作为主元,使算法运行时间退化为O(n^2)),采用特殊的主元选择,称为中位数的中位数算法。在最坏情况和平均情况下,整个解在O(n)时间内运行。
这里是全文的链接(它是关于寻找第k个最小的元素,但寻找第k个最大的元素的原理是相同的):
在无序数组中寻找第k个最小元素
它类似于快速排序策略,在快速排序策略中,我们选择一个任意的枢轴,并将较小的元素放在它的左边,将较大的元素放在右边
public static int kthElInUnsortedList(List<int> list, int k)
{
if (list.Count == 1)
return list[0];
List<int> left = new List<int>();
List<int> right = new List<int>();
int pivotIndex = list.Count / 2;
int pivot = list[pivotIndex]; //arbitrary
for (int i = 0; i < list.Count && i != pivotIndex; i++)
{
int currentEl = list[i];
if (currentEl < pivot)
left.Add(currentEl);
else
right.Add(currentEl);
}
if (k == left.Count + 1)
return pivot;
if (left.Count < k)
return kthElInUnsortedList(right, k - left.Count - 1);
else
return kthElInUnsortedList(left, k);
}