我相信有一种方法可以在 O(n) 中找到长度为 n 的未排序数组中的第 k 个最大元素。或者也许它是“预期的” O(n) 或其他东西。我们应该怎么做？
MrDatabase
问问题
238173 次
33 回答
176
这称为找到第k 阶统计量。有一个非常简单的随机算法（称为quickselect）采用O(n)平均时间、O(n^2)最坏情况时间，还有一个非常复杂的非随机算法（称为introselect）采用O(n)最坏情况时间。维基百科上有一些信息，但不是很好。
您需要的一切都在这些 powerpoint 幻灯片中。只是为了提取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 等人的《算法简介》一书中也非常详细地介绍了这一点。
于 2008-10-30T21:48:05.517 回答
121
如果你想要一个真正的O(n)算法，而不是O(kn)类似的，那么你应该使用快速选择（它基本上是快速排序，你扔掉你不感兴趣的分区）。我的教授写了一篇很棒的文章，带有运行时分析：（参考）
QuickSelect 算法快速找到未排序的元素数组中的第 k 个最小n元素。它是一个RandomizedAlgorithm，因此我们计算最坏情况下的预期运行时间。
这是算法。
QuickSelect(A, k)
let r be chosen uniformly at random in the range 1 to length(A)
let pivot = A[r]
let A1, A2 be new arrays
# split into a pile A1 of small elements and A2 of big elements
for i = 1 to n
if A[i] < pivot then
append A[i] to A1
else if A[i] > pivot then
append A[i] to A2
else
# do nothing
end for
if k <= length(A1):
# it's in the pile of small elements
return QuickSelect(A1, k)
else if k > length(A) - length(A2)
# it's in the pile of big elements
return QuickSelect(A2, k - (length(A) - length(A2))
else
# it's equal to the pivot
return pivot
这个算法的运行时间是多少？如果对手为我们抛硬币，我们可能会发现枢轴始终是最大元素并且k始终为 1，运行时间为
T(n) = Theta(n) + T(n-1) = Theta(n2)但如果选择确实是随机的，则预期运行时间由下式给出
T(n) <= Theta(n) + (1/n) ∑<sub>i=1 to nT(max(i, n-i-1))我们做出了一个不完全合理的假设，即递归总是落在 or 中的较大A1者A2。
让我们猜测T(n) <= an一下a。然后我们得到
T(n)
<= cn + (1/n) ∑<sub>i=1 to nT(max(i-1, n-i))
= cn + (1/n) ∑<sub>i=1 to floor(n/2) T(n-i) + (1/n) ∑<sub>i=floor(n/2)+1 to n T(i)
<= cn + 2 (1/n) ∑<sub>i=floor(n/2) to n T(i)
<= cn + 2 (1/n) ∑<sub>i=floor(n/2) to n ai现在不知何故，我们必须在加号右边得到可怕的总和来吸收cn左边的。如果我们只是将它绑定为2(1/n) ∑<sub>i=n/2 to n an，我们会得到粗略2(1/n)(n/2)an = an的 . 但这太大了 - 没有空间可以挤入额外的cn. 因此，让我们使用算术级数公式扩展总和：
∑<sub>i=floor(n/2) to n i
= ∑<sub>i=1 to n i - ∑<sub>i=1 to floor(n/2) i
= n(n+1)/2 - floor(n/2)(floor(n/2)+1)/2
<= n2/2 - (n/4)2/2
= (15/32)n2我们利用 n 的“足够大”来用floor(n/2)更干净（更小）的来替换丑陋的因素n/4。现在我们可以继续
cn + 2 (1/n) ∑<sub>i=floor(n/2) to n ai,
<= cn + (2a/n) (15/32) n2
= n (c + (15/16)a)
<= an提供a > 16c.
这给了T(n) = O(n). 很明显Omega(n)，所以我们得到了T(n) = Theta(n)。
于 2008-10-31T22:23:11.870 回答
15
一个快速的谷歌（'第k大元素数组'）返回了这个：http ://discuss.joelonsoftware.com/default.asp?interview.11.509587.17
"Make one pass through tracking the three largest values so far."
（它专门用于 3d 最大）
这个答案：
Build a heap/priority queue. O(n)
Pop top element. O(log n)
Pop top element. O(log n)
Pop top element. O(log n)
Total = O(n) + 3 O(log n) = O(n)
于 2008-10-30T21:12:11.690 回答
11
你确实喜欢快速排序。随机选择一个元素并将所有内容推高或推低。此时你会知道你实际选择了哪个元素，如果它是你完成的第 k 个元素，否则你用 bin 重复（更高或更低），第 k 个元素会落入。从统计学上讲，时间需要找到第 k 个元素随 n 增长，O(n)。
于 2010-06-23T02:14:15.787 回答
6
A Programmer's Companion to Algorithm Analysis给出了 O(n) 的版本，尽管作者指出常数因子如此之高，但您可能更喜欢简单的 sort-the-list-then-select 方法。
我回答了你的问题的信:)
于 2008-10-30T21:17:23.210 回答
5
C++ 标准库几乎完全具有该函数调用nth_element，尽管它确实修改了您的数据。它预计线性运行时间 O(N)，并且还进行部分排序。
const int N = ...;
double a[N];
// ...
const int m = ...; // m < N
nth_element (a, a + m, a + N);
// a[m] contains the mth element in a
于 2008-10-30T22:53:51.923 回答
4
我使用动态编程，特别是锦标赛方法，实现了在 n 个未排序元素中找到第 k 个最小值。执行时间为 O(n + klog(n))。使用的机制被列为维基百科页面上关于选择算法的方法之一（如上面的帖子之一所示）。您可以在我的博客页面Finding Kth Minimum上阅读有关该算法的信息并找到代码 (java) 。此外，该逻辑可以对列表进行部分排序 - 在 O(klog(n)) 时间内返回第一个 K min（或 max）。
尽管代码提供了第 k 个最小值，但可以使用类似的逻辑在 O(klog(n)) 中找到第 k 个最大值，忽略为创建锦标赛树所做的准备工作。
于 2011-01-04T05:43:15.603 回答
4
虽然不太确定 O(n) 复杂度，但肯定会在 O(n) 和 nLog(n) 之间。也肯定比 nLog(n) 更接近 O(n)。函数是用Java编写的
public int quickSelect(ArrayList<Integer>list, int nthSmallest){
//Choose random number in range of 0 to array length
Random random = new Random();
//This will give random number which is not greater than length - 1
int pivotIndex = random.nextInt(list.size() - 1);
int pivot = list.get(pivotIndex);
ArrayList<Integer> smallerNumberList = new ArrayList<Integer>();
ArrayList<Integer> greaterNumberList = new ArrayList<Integer>();
//Split list into two.
//Value smaller than pivot should go to smallerNumberList
//Value greater than pivot should go to greaterNumberList
//Do nothing for value which is equal to pivot
for(int i=0; i<list.size(); i++){
if(list.get(i)<pivot){
smallerNumberList.add(list.get(i));
}
else if(list.get(i)>pivot){
greaterNumberList.add(list.get(i));
}
else{
//Do nothing
}
}
//If smallerNumberList size is greater than nthSmallest value, nthSmallest number must be in this list
if(nthSmallest < smallerNumberList.size()){
return quickSelect(smallerNumberList, nthSmallest);
}
//If nthSmallest is greater than [ list.size() - greaterNumberList.size() ], nthSmallest number must be in this list
//The step is bit tricky. If confusing, please see the above loop once again for clarification.
else if(nthSmallest > (list.size() - greaterNumberList.size())){
//nthSmallest will have to be changed here. [ list.size() - greaterNumberList.size() ] elements are already in
//smallerNumberList
nthSmallest = nthSmallest - (list.size() - greaterNumberList.size());
return quickSelect(greaterNumberList,nthSmallest);
}
else{
return pivot;
}
}
于 2011-08-18T07:25:06.610 回答
3
通过跟踪您见过的 k 个最大元素，您可以在 O(n + kn) = O(n)（对于常数 k）和空间的 O(k) 中做到这一点。
对于数组中的每个元素，您可以扫描 k 最大的列表，如果它更大，则用新元素替换最小的元素。
不过，Warren 的优先堆解决方案更简洁。
于 2008-10-30T21:17:49.777 回答
3
Python中的性感快速选择
def quickselect(arr, k):
'''
k = 1 returns first element in ascending order.
can be easily modified to return first element in descending order
'''
r = random.randrange(0, len(arr))
a1 = [i for i in arr if i < arr[r]] '''partition'''
a2 = [i for i in arr if i > arr[r]]
if k <= len(a1):
return quickselect(a1, k)
elif k > len(arr)-len(a2):
return quickselect(a2, k - (len(arr) - len(a2)))
else:
return arr[r]
于 2014-07-22T16:52:28.497 回答
3
根据本文在 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后半部分）。该算法cn在某个常数的第一级递归c、cn/2下一级（因为我们在大小为 n/2 的列表中递归）、cn/4第三级等都需要时间。花费的总时间是cn + cn/2 + cn/4 + .... = 2cn = o(n)。
为什么分区大小取 5 而不是 3？
如原始论文中所述：
将列表除以 5 可确保在最坏情况下拆分为 70 - 30。中位数的至少一半大于中位数的中位数，因此 n/5 块中的至少一半具有至少 3 个元素，这给出了
3n/10拆分，这意味着在最坏的情况下另一个分区是 7n/10。也就是说T(n) = T(n/5)+T(7n/10)+O(n). Since n/5+7n/10 < 1，最坏情况下的运行时间是O(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
于 2015-09-04T09:09:57.157 回答
2
在线性时间内找到数组的中位数，然后使用与快速排序完全相同的分区过程将数组分成两部分，中位数左侧的值小于（<）小于中位数，右侧大于（>）中位数，这也可以在线性时间完成，现在，转到第 k 个元素所在的数组部分，现在递归变为：T(n) = T(n/2) + cn，这给了我 O(n) 总体。
于 2010-04-18T18:21:39.587 回答
2
下面是完整实现的链接，其中包含相当广泛的解释，用于在未排序算法中查找第 K 个元素的算法如何工作。基本思想是像快速排序一样对数组进行分区。但是为了避免极端情况（例如，当每个步骤中选择最小元素作为枢轴时，使得算法退化为 O(n^2) 运行时间），应用了特殊的枢轴选择，称为中位数算法。在最坏和平均情况下，整个解决方案在 O(n) 时间内运行。
这是完整文章的链接（它是关于寻找第 Kth 个最小元素，但寻找第 Kth 个最大元素的原理是相同的）：
于 2013-07-19T09:17:41.933 回答
2
这种方法怎么样
保持 abuffer of length k和 a tmp_max，得到 tmp_max 是 O(k) 并且完成 n 次，所以类似于O(kn)
是对的还是我错过了什么？
虽然它没有击败快速选择的平均情况和中值统计方法的最坏情况，但它很容易理解和实现。
于 2016-06-16T09:55:13.347 回答
1
遍历列表。如果当前值大于存储的最大值，则将其存储为最大值并将 1-4 向下和 5 从列表中删除。如果不是，将其与 2 号进行比较并做同样的事情。重复，对照所有 5 个存储值检查它。这应该在 O(n) 中完成
于 2008-10-30T21:10:13.583 回答
1
我想提出一个答案
如果我们取前 k 个元素并将它们排序到 k 个值的链表中
现在对于每个其他值，即使在最坏的情况下，如果我们对剩余的 nk 值进行插入排序，即使在最坏的情况下，比较的数量也将是 k*(nk)，对于要排序的前 k 个值，让它成为 k*(k- 1) 所以结果是 (nk-k)，即 o(n)
干杯
于 2009-07-31T16:51:47.017 回答
1
可以在此处找到用于查找 n 中第 k 个最大整数的中位数算法的解释：http: //cs.indstate.edu/~spitla/presentation.pdf
c++中的实现如下：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int findMedian(vector<int> vec){
// Find median of a vector
int median;
size_t size = vec.size();
median = vec[(size/2)];
return median;
}
int findMedianOfMedians(vector<vector<int> > values){
vector<int> medians;
for (int i = 0; i < values.size(); i++) {
int m = findMedian(values[i]);
medians.push_back(m);
}
return findMedian(medians);
}
void selectionByMedianOfMedians(const vector<int> values, int k){
// Divide the list into n/5 lists of 5 elements each
vector<vector<int> > vec2D;
int count = 0;
while (count != values.size()) {
int countRow = 0;
vector<int> row;
while ((countRow < 5) && (count < values.size())) {
row.push_back(values[count]);
count++;
countRow++;
}
vec2D.push_back(row);
}
cout<<endl<<endl<<"Printing 2D vector : "<<endl;
for (int i = 0; i < vec2D.size(); i++) {
for (int j = 0; j < vec2D[i].size(); j++) {
cout<<vec2D[i][j]<<" ";
}
cout<<endl;
}
cout<<endl;
// Calculating a new pivot for making splits
int m = findMedianOfMedians(vec2D);
cout<<"Median of medians is : "<<m<<endl;
// Partition the list into unique elements larger than 'm' (call this sublist L1) and
// those smaller them 'm' (call this sublist L2)
vector<int> L1, L2;
for (int i = 0; i < vec2D.size(); i++) {
for (int j = 0; j < vec2D[i].size(); j++) {
if (vec2D[i][j] > m) {
L1.push_back(vec2D[i][j]);
}else if (vec2D[i][j] < m){
L2.push_back(vec2D[i][j]);
}
}
}
// Checking the splits as per the new pivot 'm'
cout<<endl<<"Printing L1 : "<<endl;
for (int i = 0; i < L1.size(); i++) {
cout<<L1[i]<<" ";
}
cout<<endl<<endl<<"Printing L2 : "<<endl;
for (int i = 0; i < L2.size(); i++) {
cout<<L2[i]<<" ";
}
// Recursive calls
if ((k - 1) == L1.size()) {
cout<<endl<<endl<<"Answer :"<<m;
}else if (k <= L1.size()) {
return selectionByMedianOfMedians(L1, k);
}else if (k > (L1.size() + 1)){
return selectionByMedianOfMedians(L2, k-((int)L1.size())-1);
}
}
int main()
{
int values[] = {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};
vector<int> vec(values, values + 25);
cout<<"The given array is : "<<endl;
for (int i = 0; i < vec.size(); i++) {
cout<<vec[i]<<" ";
}
selectionByMedianOfMedians(vec, 8);
return 0;
}
于 2013-02-28T19:50:18.780 回答
1
还有Wirth 的选择算法，它的实现比 QuickSelect 更简单。Wirth 的选择算法比 QuickSelect 慢，但经过一些改进，它变得更快。
更详细。使用 Vladimir Zabrodsky 的 MODIFIND 优化和中值 3 枢轴选择并注意算法分区部分的最后步骤，我提出了以下算法（可以想象命名为“LefSelect”）：
#define F_SWAP(a,b) { float temp=(a);(a)=(b);(b)=temp; }
# Note: The code needs more than 2 elements to work
float lefselect(float a[], const int n, const int k) {
int l=0, m = n-1, i=l, j=m;
float x;
while (l<m) {
if( a[k] < a[i] ) F_SWAP(a[i],a[k]);
if( a[j] < a[i] ) F_SWAP(a[i],a[j]);
if( a[j] < a[k] ) F_SWAP(a[k],a[j]);
x=a[k];
while (j>k & i<k) {
do i++; while (a[i]<x);
do j--; while (a[j]>x);
F_SWAP(a[i],a[j]);
}
i++; j--;
if (j<k) {
while (a[i]<x) i++;
l=i; j=m;
}
if (k<i) {
while (x<a[j]) j--;
m=j; i=l;
}
}
return a[k];
}
在我在这里做的基准测试中，LefSelect 比 QuickSelect 快 20-30%。
于 2014-11-03T23:15:27.967 回答
1
哈斯克尔解决方案：
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 方法在不实际计算分区的情况下发现分区的大小来实现中位数解的中位数。
于 2015-01-23T23:42:31.793 回答
1
这是 Randomized QuickSelect 的 C++ 实现。这个想法是随机选择一个枢轴元素。为了实现随机分区，我们使用随机函数 rand() 生成 l 和 r 之间的索引，将随机生成的索引处的元素与最后一个元素交换，最后调用以最后一个元素为基准的标准分区过程。
#include<iostream>
#include<climits>
#include<cstdlib>
using namespace std;
int randomPartition(int arr[], int l, int r);
// This function returns k'th smallest element in arr[l..r] using
// QuickSort based method. ASSUMPTION: ALL ELEMENTS IN ARR[] ARE DISTINCT
int kthSmallest(int arr[], int l, int r, int k)
{
// If k is smaller than number of elements in array
if (k > 0 && k <= r - l + 1)
{
// Partition the array around a random element and
// get position of pivot element in sorted array
int pos = randomPartition(arr, l, r);
// If position is same as k
if (pos-l == k-1)
return arr[pos];
if (pos-l > k-1) // If position is more, recur for left subarray
return kthSmallest(arr, l, pos-1, k);
// Else recur for right subarray
return kthSmallest(arr, pos+1, r, k-pos+l-1);
}
// If k is more than number of elements in array
return INT_MAX;
}
void swap(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}
// Standard partition process of QuickSort(). It considers the last
// element as pivot and moves all smaller element to left of it and
// greater elements to right. This function is used by randomPartition()
int partition(int arr[], int l, int r)
{
int x = arr[r], i = l;
for (int j = l; j <= r - 1; j++)
{
if (arr[j] <= x) //arr[i] is bigger than arr[j] so swap them
{
swap(&arr[i], &arr[j]);
i++;
}
}
swap(&arr[i], &arr[r]); // swap the pivot
return i;
}
// Picks a random pivot element between l and r and partitions
// arr[l..r] around the randomly picked element using partition()
int randomPartition(int arr[], int l, int r)
{
int n = r-l+1;
int pivot = rand() % n;
swap(&arr[l + pivot], &arr[r]);
return partition(arr, l, r);
}
// Driver program to test above methods
int main()
{
int arr[] = {12, 3, 5, 7, 4, 19, 26};
int n = sizeof(arr)/sizeof(arr[0]), k = 3;
cout << "K'th smallest element is " << kthSmallest(arr, 0, n-1, k);
return 0;
}
上述解决方案的最坏情况时间复杂度仍然是 O(n2)。在最坏情况下，随机函数可能总是选择一个角元素。上述随机快速选择的预期时间复杂度为 Θ(n)
于 2015-04-19T11:47:20.393 回答
1
- 已创建优先队列。
- 将所有元素插入堆中。
调用 poll() k 次。
public static int getKthLargestElements(int[] arr) { PriorityQueue<Integer> pq = new PriorityQueue<>((x , y) -> (y-x)); //insert all the elements into heap for(int ele : arr) pq.offer(ele); // call poll() k times int i=0; while(i<k) { int result = pq.poll(); } return result; }
于 2016-10-24T04:17:39.953 回答
1
还有一种算法优于快速选择算法。它被称为弗洛伊德铆钉（FR）算法。
原文：https ://doi.org/10.1145/360680.360694
可下载版本：http ://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.309.7108&rep=rep1&type=pdf
维基百科文章https://en.wikipedia.org/wiki/Floyd%E2%80%93Rivest_algorithm
我尝试在 C++ 中实现快速选择和 FR 算法。此外，我将它们与标准 C++ 库实现 std::nth_element （基本上是快速选择和堆选择的 introselect 混合）进行了比较。结果是快速选择和 nth_element 平均运行相当，但 FR 算法运行大约。比他们快两倍。
我用于 FR 算法的示例代码：
template <typename T>
T FRselect(std::vector<T>& data, const size_t& n)
{
if (n == 0)
return *(std::min_element(data.begin(), data.end()));
else if (n == data.size() - 1)
return *(std::max_element(data.begin(), data.end()));
else
return _FRselect(data, 0, data.size() - 1, n);
}
template <typename T>
T _FRselect(std::vector<T>& data, const size_t& left, const size_t& right, const size_t& n)
{
size_t leftIdx = left;
size_t rightIdx = right;
while (rightIdx > leftIdx)
{
if (rightIdx - leftIdx > 600)
{
size_t range = rightIdx - leftIdx + 1;
long long i = n - (long long)leftIdx + 1;
long long z = log(range);
long long s = 0.5 * exp(2 * z / 3);
long long sd = 0.5 * sqrt(z * s * (range - s) / range) * sgn(i - (long long)range / 2);
size_t newLeft = fmax(leftIdx, n - i * s / range + sd);
size_t newRight = fmin(rightIdx, n + (range - i) * s / range + sd);
_FRselect(data, newLeft, newRight, n);
}
T t = data[n];
size_t i = leftIdx;
size_t j = rightIdx;
// arrange pivot and right index
std::swap(data[leftIdx], data[n]);
if (data[rightIdx] > t)
std::swap(data[rightIdx], data[leftIdx]);
while (i < j)
{
std::swap(data[i], data[j]);
++i; --j;
while (data[i] < t) ++i;
while (data[j] > t) --j;
}
if (data[leftIdx] == t)
std::swap(data[leftIdx], data[j]);
else
{
++j;
std::swap(data[j], data[rightIdx]);
}
// adjust left and right towards the boundaries of the subset
// containing the (k - left + 1)th smallest element
if (j <= n)
leftIdx = j + 1;
if (n <= j)
rightIdx = j - 1;
}
return data[leftIdx];
}
template <typename T>
int sgn(T val) {
return (T(0) < val) - (val < T(0));
}
于 2018-02-16T11:39:16.913 回答
0
这是 Javascript 中的一个实现。
如果释放不能修改数组的约束，可以防止使用额外的内存使用两个索引来标识“当前分区”（经典快速排序风格 - http://www.nczonline.net/blog/2012/ 11/27/computer-science-in-javascript-quicksort/）。
function kthMax(a, k){
var size = a.length;
var pivot = a[ parseInt(Math.random()*size) ]; //Another choice could have been (size / 2)
//Create an array with all element lower than the pivot and an array with all element higher than the pivot
var i, lowerArray = [], upperArray = [];
for (i = 0; i < size; i++){
var current = a[i];
if (current < pivot) {
lowerArray.push(current);
} else if (current > pivot) {
upperArray.push(current);
}
}
//Which one should I continue with?
if(k <= upperArray.length) {
//Upper
return kthMax(upperArray, k);
} else {
var newK = k - (size - lowerArray.length);
if (newK > 0) {
///Lower
return kthMax(lowerArray, newK);
} else {
//None ... it's the current pivot!
return pivot;
}
}
}
如果你想测试它的表现，你可以使用这个变体：
function kthMax (a, k, logging) {
var comparisonCount = 0; //Number of comparison that the algorithm uses
var memoryCount = 0; //Number of integers in memory that the algorithm uses
var _log = logging;
if(k < 0 || k >= a.length) {
if (_log) console.log ("k is out of range");
return false;
}
function _kthmax(a, k){
var size = a.length;
var pivot = a[parseInt(Math.random()*size)];
if(_log) console.log("Inputs:", a, "size="+size, "k="+k, "pivot="+pivot);
// This should never happen. Just a nice check in this exercise
// if you are playing with the code to avoid never ending recursion
if(typeof pivot === "undefined") {
if (_log) console.log ("Ops...");
return false;
}
var i, lowerArray = [], upperArray = [];
for (i = 0; i < size; i++){
var current = a[i];
if (current < pivot) {
comparisonCount += 1;
memoryCount++;
lowerArray.push(current);
} else if (current > pivot) {
comparisonCount += 2;
memoryCount++;
upperArray.push(current);
}
}
if(_log) console.log("Pivoting:",lowerArray, "*"+pivot+"*", upperArray);
if(k <= upperArray.length) {
comparisonCount += 1;
return _kthmax(upperArray, k);
} else if (k > size - lowerArray.length) {
comparisonCount += 2;
return _kthmax(lowerArray, k - (size - lowerArray.length));
} else {
comparisonCount += 2;
return pivot;
}
/*
* BTW, this is the logic for kthMin if we want to implement that... ;-)
*
if(k <= lowerArray.length) {
return kthMin(lowerArray, k);
} else if (k > size - upperArray.length) {
return kthMin(upperArray, k - (size - upperArray.length));
} else
return pivot;
*/
}
var result = _kthmax(a, k);
return {result: result, iterations: comparisonCount, memory: memoryCount};
}
其余的代码只是创建一些游乐场：
function getRandomArray (n){
var ar = [];
for (var i = 0, l = n; i < l; i++) {
ar.push(Math.round(Math.random() * l))
}
return ar;
}
//Create a random array of 50 numbers
var ar = getRandomArray (50);
现在，运行你的测试几次。由于 Math.random() 每次都会产生不同的结果：
kthMax(ar, 2, true);
kthMax(ar, 2);
kthMax(ar, 2);
kthMax(ar, 2);
kthMax(ar, 2);
kthMax(ar, 2);
kthMax(ar, 34, true);
kthMax(ar, 34);
kthMax(ar, 34);
kthMax(ar, 34);
kthMax(ar, 34);
kthMax(ar, 34);
如果您对其进行几次测试，您甚至可以根据经验看到迭代次数平均为 O(n) ~= constant * n 并且 k 的值不会影响算法。
于 2013-09-30T08:13:27.303 回答
0
我想出了这个算法，似乎是 O(n)：
假设 k=3，我们想在数组中找到第三大的项目。我将创建三个变量并将数组的每个项目与这三个变量中的最小值进行比较。如果数组 item 大于我们的最小值，我们将用 item 值替换 min 变量。我们继续同样的事情直到数组结束。我们三个变量中的最小值是数组中的第三大项。
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
有人可以查看这个并让我知道我缺少什么吗？
于 2015-08-06T17:23:24.187 回答
0
这是eladv建议的算法的实现（我也在这里放了随机枢轴的实现）：
public class Median {
public static void main(String[] s) {
int[] test = {4,18,20,3,7,13,5,8,2,1,15,17,25,30,16};
System.out.println(selectK(test,8));
/*
int n = 100000000;
int[] test = new int[n];
for(int i=0; i<test.length; i++)
test[i] = (int)(Math.random()*test.length);
long start = System.currentTimeMillis();
random_selectK(test, test.length/2);
long end = System.currentTimeMillis();
System.out.println(end - start);
*/
}
public static int random_selectK(int[] a, int k) {
if(a.length <= 1)
return a[0];
int r = (int)(Math.random() * a.length);
int p = a[r];
int small = 0, equal = 0, big = 0;
for(int i=0; i<a.length; i++) {
if(a[i] < p) small++;
else if(a[i] == p) equal++;
else if(a[i] > p) big++;
}
if(k <= small) {
int[] temp = new int[small];
for(int i=0, j=0; i<a.length; i++)
if(a[i] < p)
temp[j++] = a[i];
return random_selectK(temp, k);
}
else if (k <= small+equal)
return p;
else {
int[] temp = new int[big];
for(int i=0, j=0; i<a.length; i++)
if(a[i] > p)
temp[j++] = a[i];
return random_selectK(temp,k-small-equal);
}
}
public static int selectK(int[] a, int k) {
if(a.length <= 5) {
Arrays.sort(a);
return a[k-1];
}
int p = median_of_medians(a);
int small = 0, equal = 0, big = 0;
for(int i=0; i<a.length; i++) {
if(a[i] < p) small++;
else if(a[i] == p) equal++;
else if(a[i] > p) big++;
}
if(k <= small) {
int[] temp = new int[small];
for(int i=0, j=0; i<a.length; i++)
if(a[i] < p)
temp[j++] = a[i];
return selectK(temp, k);
}
else if (k <= small+equal)
return p;
else {
int[] temp = new int[big];
for(int i=0, j=0; i<a.length; i++)
if(a[i] > p)
temp[j++] = a[i];
return selectK(temp,k-small-equal);
}
}
private static int median_of_medians(int[] a) {
int[] b = new int[a.length/5];
int[] temp = new int[5];
for(int i=0; i<b.length; i++) {
for(int j=0; j<5; j++)
temp[j] = a[5*i + j];
Arrays.sort(temp);
b[i] = temp[2];
}
return selectK(b, b.length/2 + 1);
}
}
于 2016-06-02T09:05:39.030 回答
0
它类似于快速排序策略，我们选择一个任意的枢轴，并将较小的元素放在其左侧，将较大的元素放在右侧
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);
}
于 2016-07-01T10:30:26.587 回答
0
转到此链接的末尾：......
于 2016-07-25T17:03:47.067 回答
0
您可以在 O(n) 时间和常数空间中找到第 k 个最小的元素。如果我们认为数组仅用于整数。
该方法是对 Array 值的范围进行二进制搜索。如果我们有一个 min_value 和一个 max_value 都在整数范围内，我们可以在该范围内进行二进制搜索。我们可以编写一个比较器函数，它会告诉我们任何值是否是第 k 小或小于第 k 小或大于第 k 小。进行二分查找，直到找到第 k 个最小的数
这是代码
类解决方案：
def _iskthsmallest(self, A, val, k):
less_count, equal_count = 0, 0
for i in range(len(A)):
if A[i] == val: equal_count += 1
if A[i] < val: less_count += 1
if less_count >= k: return 1
if less_count + equal_count < k: return -1
return 0
def kthsmallest_binary(self, A, min_val, max_val, k):
if min_val == max_val:
return min_val
mid = (min_val + max_val)/2
iskthsmallest = self._iskthsmallest(A, mid, k)
if iskthsmallest == 0: return mid
if iskthsmallest > 0: return self.kthsmallest_binary(A, min_val, mid, k)
return self.kthsmallest_binary(A, mid+1, max_val, k)
# @param A : tuple of integers
# @param B : integer
# @return an integer
def kthsmallest(self, A, k):
if not A: return 0
if k > len(A): return 0
min_val, max_val = min(A), max(A)
return self.kthsmallest_binary(A, min_val, max_val, k)
于 2017-10-31T21:45:00.247 回答
0
第 k 个最大元素意味着，我们需要对数组进行排序，然后从数组末尾倒数。例如
const array= [2, 32, 12, 3, 78, 99, 898, 8, 1] // we need to sort this
const sortedArray= [1, 2, 3, 8, 12, 32, 78, 99, 898]
第 5 个最大元素意味着从最后倒数 5 个元素，即 12。
默认情况下，大多数语言实现快速排序或合并排序，因为它们是最优化的排序。我用快速排序解决了这个问题。快速排序对数组进行就地排序，它不会给我们返回一个新数组，并且像合并排序一样它是递归的。快速排序的缺点，在最坏的情况下，它的时间复杂度是 O(n**2) "n square"。
快速排序是分治算法，通过解决其所有较小的组件来解决问题。我们选择最后一个元素作为枢轴元素（有些算法选择第一个元素作为枢轴，有些算法在开始时选择最后一个元素）。枢轴元素是分区元素。这是我们的数组=[2, 32, 12, 3, 78, 99, 898, 8, 1]
我们使用 2 个指针，i,j 从第一个元素开始。"i" 跟踪枢轴的最终位置。
i=j=2 //starting point
“j”将扫描数组，并将每个元素与枢轴进行比较。如果“j”小于pivot，我们将交换“i”和“j”并将“i”和“j”向前移动。当“j”到达枢轴时，我们将“i”与枢轴交换。在我们的示例中，pivot 是1，1 是较小的数字，“j”将在pivot=1不交换“i”、“j”的情况下到达 。请记住，“i”是枢轴的占位符。因此，当“j”到达枢轴时，1 和 2 将被交换。
此操作的目的是找到所有小于其左侧枢轴的元素。请注意，枢轴左侧的所有元素都小于枢轴，但左侧未排序。然后我们将数组从枢轴分成 2 个子数组并递归地应用快速排序。
const quickSort = function (array, left, right) {
// if left=right, it means we have only one item, it is already sorted
if (left < right) {
const partitionIndex = partition(array, left, right);
quickSort(array, left, partitionIndex - 1);
quickSort(array, partitionIndex + 1, right);
}
};
使用“i”和“j”指针，这就是我们找到分区索引的方式
const partition = function (array, left, right) {
const pivotElement = array[right];
let partitionIndex = left;
for (let j = left; j < right; j++) {
if (array[j] < pivotElement) {
swap(array, partitionIndex, j);
partitionIndex++;
}
}
// if none of the "j" values is smaller than pivot, when "j" reaches the pivot, we swap "i'th" element with pivot
swap(array, partitionIndex, right);
return partitionIndex;
};
这是交换功能的简单实现：
const swap = function (array, i, j) {
const temp = array[i];
array[i] = array[j];
array[j] = temp;
};
于 2021-02-06T03:04:23.567 回答
0
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);
于 2021-09-07T00:30:30.463 回答
-1
我要做的是：
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
于 2008-10-30T21:19:00.757 回答
-1
首先，我们可以从需要 O(n) 时间的未排序数组构建 BST，并且从 BST 中我们可以找到 O(log(n)) 中的第 k 个最小元素，该元素的总计数为 O(n)。
于 2013-09-17T11:30:12.817 回答
-2
对于非常小的 k 值（即当 k << n），我们可以在 ~O(n) 时间内完成。否则，如果 k 与 n 相当，我们在 O(nlogn) 中得到它。
于 2012-10-05T05:21:15.823 回答