我正在尝试使用 C++ 中的快速选择来执行此操作,但它总是返回第 k 个最小的元素而不是第 k 个最大的元素。我的逻辑哪里错了?
int partition(int* input, int p, int r)
{
int pivot = input[r];
while ( p < r )
{
while ( input[p] < pivot )
p++;
while ( input[r] > pivot )
r--;
if ( input[p] == input[r] )
p++;
else if ( p < r ) {
int tmp = input[p];
input[p] = input[r];
input[r] = tmp;
}
}
return r;
}
int quick_select(int* input, int p, int r, int k)
{
if ( p == r ) return input[p];
int j = partition(input, p, r);
int length = j - p + 1;
if ( length == k ) return input[j];
else if ( k < length ) return quick_select(input, p, j - 1, k);
else return quick_select(input, j + 1, r, k - length);
}
我应该更改什么才能使这个第 k 个最大而不是第 k 个最小的元素?
最佳答案
<
和 >
在你的代码中是相反的 partition()
正如@Dietmar Kühl 提到的,通过更改它们,它可以正常工作。
另外,我的建议是使用普通的partition()
如下所示的快速排序,其两个索引向同一方向移动,并且其中一个永远不会超过另一个。让任何人感到困惑并不容易。
int partition(int *input, int p, int r) {
int pivot,i,j,tmp;
pivot = input[r];
i = p-1;
for (j=p;j<=r-1;j++) {
if (input[j]>= pivot) {
i++;
tmp = input[i];
input[i] = input[j];
input[j] = tmp;
}
}
tmp = input[i+1];
input[i+1] = input[r];
input[r] = tmp;
return i+1;
}
关于c++ - 在数组中找到第 K 个最大的整数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/18436142/