Найти Kth самый большой int в массиве
Я пытаюсь использовать quickselect в 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;
}
Другие решения
Других решений пока нет …