K-ая порядковая статистика (реализация на языке C++)

C++   28 марта 2012  Автор статьи:  

Функция kth(int l, int r, int k) находит k-ую порядковую статистику на отрезке [l;r] в массиве long long arr. Для этого используется модификация быстрой сортировки, только вместо того, чтобы сортировать весь массив, мы занимаемся поиском k-ого элемента в отсортированном массиве.

long long kth(int l,int r,int k)
{
long long x = arr[(l+r) / 2];
int i=l,j=r;
while(i<=j) { while(arr[i] < x) i++; while(arr[j] > x) j--;

if(i<=j) { swap(arr[i],arr[j]); i++; j--; } } if(l<=k && k<=j) return kth(l,j,k); if( i<=k && k<=r) return kth(i,r,k); return arr[k]; }

  • макс

    Какая сложность?

    • В среднем за O(n) работает.

Научиться программировать

  • на Delphi

  • на Java

  • на C++