MAXimal | |
добавлено: 11 Jun 2008 11:07 Содержание [скрыть] K-ая порядковая статистика за O (N)Пусть дан массив A длиной N и пусть дано число K. Задача заключается в том, чтобы найти в этом массиве K-ое по величине число, т.е. K-ую порядковую статистику.
Основная идея - использовать идеи алгоритма быстрой сортировки. Собственно, алгоритм несложный, сложнее доказать, что он работает в среднем за O (N), в отличие от быстрой сортировки.
Реализация в виде нерекурсивной функции: template <class T> T order_statistics (std::vector<T> a, unsigned n, unsigned k) { using std::swap; for (unsigned l=1, r=n; ; ) { if (r <= l+1) { // текущая часть состоит из 1 или 2 элементов - // легко можем найти ответ if (r == l+1 && a[r] < a[l]) swap (a[l], a[r]); return a[k]; } // упорядочиваем a[l], a[l+1], a[r] unsigned mid = (l + r) >> 1; swap (a[mid], a[l+1]); if (a[l] > a[r]) swap (a[l], a[r]); if (a[l+1] > a[r]) swap (a[l+1], a[r]); if (a[l] > a[l+1]) swap (a[l], a[l+1]); // выполняем разделение // барьером является a[l+1], т.е. медиана среди a[l], a[l+1], a[r] unsigned i = l+1, j = r; const T cur = a[l+1]; for (;;) { while (a[++i] < cur) ; while (a[--j] > cur) ; if (i > j) break; swap (a[i], a[j]); } // вставляем барьер a[l+1] = a[j]; a[j] = cur; // продолжаем работать в той части, // которая должна содержать искомый элемент if (j >= k) r = j-1; if (j <= k) l = i; } }
Следует заметить, что в стандартной библиотеке C++ этот алгоритм уже реализован - он называется nth_element.
|