我相信有一种方法可以找到长度为n的O(n)无序数组中第k大的元素。也可能是期望O(n)之类的。我们该怎么做呢?
当前回答
我提出了这个算法,似乎是O(n):
假设k=3我们想找出数组中第三大的元素。我将创建三个变量,并将数组中的每一项与这三个变量中的最小值进行比较。如果数组item大于最小值,则用item的值替换最小值变量。我们继续做同样的事情,直到数组结束。三个变量中的最小值是数组中第三大的项。
define variables a=0, b=0, c=0
iterate through the array items
find minimum a,b,c
if item > min then replace the min variable with item value
continue until end of array
the minimum of a,b,c is our answer
为了找到第K大的项,我们需要K个变量。
例如:(k = 3)
[1,2,4,1,7,3,9,5,6,2,9,8]
Final variable values:
a=7 (answer)
b=8
c=9
有人可以审查这个,让我知道我错过了什么?
其他回答
我实现了在n个未排序元素中寻找第k个最小值的动态规划,特别是竞赛方法。执行时间为O(n + klog(n))。所使用的机制在维基百科关于选择算法的页面上被列为方法之一(如上面的帖子之一所示)。你可以阅读算法,也可以在我的博客页面“查找k个最小值”上找到代码(java)。此外,逻辑可以对列表进行部分排序——在O(klog(n))时间内返回第一个K min(或max)。
虽然代码提供了第k个最小值的结果,但可以使用类似的逻辑来查找O(klog(n))中的第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);
}
转到这个链接的结尾:...........
http://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array-set-3-worst-case-linear-time/
遍历列表。如果当前值大于存储的最大值,则将其存储为最大值,并将1-4向下碰撞,5从列表中删除。如果不是,将它与第2条进行比较,然后做同样的事情。重复,检查所有5个存储值。应该是O(n)
A Programmer's Companion to Algorithm Analysis给出了一个O(n)的版本,尽管作者指出常数因子如此之高,您可能更喜欢简单的排序-列表-然后选择方法。
我已经回答了你的问题:)