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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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];
}

  • макс

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

    • http://cybern.ru/ lordrp

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

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

  • на Delphi

  • на Java

  • на C++