我相信有一种方法可以找到长度为n的O(n)无序数组中第k大的元素。也可能是期望O(n)之类的。我们该怎么做呢?
当前回答
它类似于快速排序策略,在快速排序策略中,我们选择一个任意的枢轴,并将较小的元素放在它的左边,将较大的元素放在右边
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);
}
其他回答
Haskell的解决方案:
kthElem index list = sort list !! index
withShape ~[] [] = []
withShape ~(x:xs) (y:ys) = x : withShape xs ys
sort [] = []
sort (x:xs) = (sort ls `withShape` ls) ++ [x] ++ (sort rs `withShape` rs)
where
ls = filter (< x)
rs = filter (>= x)
这通过使用withShape方法来实现中值解的中值,从而发现分区的大小,而无需实际计算分区大小。
你可以用O(n + kn) = O(n)(对于常数k)表示时间,用O(k)表示空间,通过跟踪你见过的最大的k个元素。
对于数组中的每个元素,您可以扫描k个最大的元素列表,并将最小的元素替换为更大的新元素。
Warren的优先级堆解决方案更简洁。
我会这样做:
initialize empty doubly linked list l
for each element e in array
if e larger than head(l)
make e the new head of l
if size(l) > k
remove last element from l
the last element of l should now be the kth largest element
您可以简单地存储指向链表中第一个和最后一个元素的指针。它们只在更新列表时更改。
更新:
initialize empty sorted tree l
for each element e in array
if e between head(l) and tail(l)
insert e into l // O(log k)
if size(l) > k
remove last element from l
the last element of l should now be the kth largest element
function nthMax(arr, nth = 1, maxNumber = Infinity) {
let large = -Infinity;
for(e of arr) {
if(e > large && e < maxNumber ) {
large = e;
} else if (maxNumber == large) {
nth++;
}
}
return nth==0 ? maxNumber: nthMax(arr, nth-1, large);
}
let array = [11,12,12,34,23,34];
let secondlargest = nthMax(array, 1);
console.log("Number:", secondlargest);
你确实喜欢快速排序。随机选择一个元素,然后将所有元素推高或推低。此时,您将知道您实际选择了哪个元素,如果它是第k个元素,您就完成了,否则您将重复bin(更高或更低),第k个元素将落在其中。从统计学上讲,找到第k个元素所需的时间随着n, O(n)而增加。