我相信有一种方法可以找到长度为n的O(n)无序数组中第k大的元素。也可能是期望O(n)之类的。我们该怎么做呢?
当前回答
这叫做求k阶统计量。有一个非常简单的随机算法(叫做quickselect),平均时间为O(n),最坏情况时间为O(n²),还有一个相当复杂的非随机算法(叫做introselect),最坏情况时间为O(n)。维基百科上有一些信息,但不是很好。
你需要的一切都在这些幻灯片里。只需提取O(n)最坏情况算法(introselect)的基本算法:
Select(A,n,i):
Divide input into ⌈n/5⌉ groups of size 5.
/* Partition on median-of-medians */
medians = array of each group’s median.
pivot = Select(medians, ⌈n/5⌉, ⌈n/10⌉)
Left Array L and Right Array G = partition(A, pivot)
/* Find ith element in L, pivot, or G */
k = |L| + 1
If i = k, return pivot
If i < k, return Select(L, k-1, i)
If i > k, return Select(G, n-k, i-k)
在Cormen等人的《算法介绍》一书中也有非常详细的描述。
其他回答
A Programmer's Companion to Algorithm Analysis给出了一个O(n)的版本,尽管作者指出常数因子如此之高,您可能更喜欢简单的排序-列表-然后选择方法。
我已经回答了你的问题:)
我会这样做:
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
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方法来实现中值解的中值,从而发现分区的大小,而无需实际计算分区大小。
下面是完整实现的链接,其中相当广泛地解释了在无序算法中查找第k个元素的算法是如何工作的。基本思想是像快速排序一样对数组进行分区。但为了避免极端情况(例如每一步都选择最小的元素作为主元,使算法运行时间退化为O(n^2)),采用特殊的主元选择,称为中位数的中位数算法。在最坏情况和平均情况下,整个解在O(n)时间内运行。
这里是全文的链接(它是关于寻找第k个最小的元素,但寻找第k个最大的元素的原理是相同的):
在无序数组中寻找第k个最小元素
根据本文,在n个项目的列表中寻找第k个最大的项目,下面的算法在最坏的情况下将花费O(n)时间。
将数组分成n/5个列表,每个列表有5个元素。 求每个5个元素的子数组的中值。 递归地找到所有中位数的中位数,记作M 将数组划分为两个子数组第一个子数组包含大于M的元素,设这个子数组为a1,而其他子数组包含小于M的元素,设这个子数组为a2。 如果k <= |a1|,返回选择(a1,k)。 k−1 = |a1|,返回M。 如果k> |a1| + 1,返回选择(a2,k−a1−1)。
分析:如原文所述:
我们使用中位数将列表分成两部分(前一半, 如果k <= n/2,反之则为后半部分)。这个算法需要 对于某个常数c,递归第一级的时间cn/2 at 下一层(因为我们在大小为n/2的列表中递归),cn/4在 第三层,以此类推。总时间为cn + cn/2 + cn/4 + .... = 2cn = o(n)。
为什么分区大小是5而不是3?
如原文所述:
将列表除以5可以保证最坏情况下70−30的分割。至少 至少一半的中位数大于中位数的中位数 n/5块中的一半至少有3个元素,这就给出了a 3n/10的分割,这意味着另一个分区在最坏情况下是7n/10。 得到T(n) = T(n/5)+T(7n/10)+O(n)由于n/5+7n/10 < 1 最差情况运行时间isO(n)。
现在我尝试将上述算法实现为:
public static int findKthLargestUsingMedian(Integer[] array, int k) {
// Step 1: Divide the list into n/5 lists of 5 element each.
int noOfRequiredLists = (int) Math.ceil(array.length / 5.0);
// Step 2: Find pivotal element aka median of medians.
int medianOfMedian = findMedianOfMedians(array, noOfRequiredLists);
//Now we need two lists split using medianOfMedian as pivot. All elements in list listOne will be grater than medianOfMedian and listTwo will have elements lesser than medianOfMedian.
List<Integer> listWithGreaterNumbers = new ArrayList<>(); // elements greater than medianOfMedian
List<Integer> listWithSmallerNumbers = new ArrayList<>(); // elements less than medianOfMedian
for (Integer element : array) {
if (element < medianOfMedian) {
listWithSmallerNumbers.add(element);
} else if (element > medianOfMedian) {
listWithGreaterNumbers.add(element);
}
}
// Next step.
if (k <= listWithGreaterNumbers.size()) return findKthLargestUsingMedian((Integer[]) listWithGreaterNumbers.toArray(new Integer[listWithGreaterNumbers.size()]), k);
else if ((k - 1) == listWithGreaterNumbers.size()) return medianOfMedian;
else if (k > (listWithGreaterNumbers.size() + 1)) return findKthLargestUsingMedian((Integer[]) listWithSmallerNumbers.toArray(new Integer[listWithSmallerNumbers.size()]), k-listWithGreaterNumbers.size()-1);
return -1;
}
public static int findMedianOfMedians(Integer[] mainList, int noOfRequiredLists) {
int[] medians = new int[noOfRequiredLists];
for (int count = 0; count < noOfRequiredLists; count++) {
int startOfPartialArray = 5 * count;
int endOfPartialArray = startOfPartialArray + 5;
Integer[] partialArray = Arrays.copyOfRange((Integer[]) mainList, startOfPartialArray, endOfPartialArray);
// Step 2: Find median of each of these sublists.
int medianIndex = partialArray.length/2;
medians[count] = partialArray[medianIndex];
}
// Step 3: Find median of the medians.
return medians[medians.length / 2];
}
为了完成,另一种算法利用优先队列,花费时间O(nlogn)。
public static int findKthLargestUsingPriorityQueue(Integer[] nums, int k) {
int p = 0;
int numElements = nums.length;
// create priority queue where all the elements of nums will be stored
PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
// place all the elements of the array to this priority queue
for (int n : nums) {
pq.add(n);
}
// extract the kth largest element
while (numElements - k + 1 > 0) {
p = pq.poll();
k++;
}
return p;
}
这两个算法都可以被测试为:
public static void main(String[] args) throws IOException {
Integer[] numbers = new Integer[]{2, 3, 5, 4, 1, 12, 11, 13, 16, 7, 8, 6, 10, 9, 17, 15, 19, 20, 18, 23, 21, 22, 25, 24, 14};
System.out.println(findKthLargestUsingMedian(numbers, 8));
System.out.println(findKthLargestUsingPriorityQueue(numbers, 8));
}
如预期输出为: 18 18