Разъяснение по быстрому выбору

Question

Что именно означает "k" в этом слайде лекций Quick Select?

Answer 1

Допустим, вы взяли номер x,

Позволять L быть набором чисел меньше чем x в массиве размер набора |L|

Позволять E быть набором чисел, равным x в массиве размер набора |E|

Позволять G быть набором чисел больше чем x в массиве размер набора |G|

Давайте представим отсортированный массив, первый |L| чисел (1 -> |L|) содержатся в наборе L,

Следующие |E| чисел (|L|+1 -> |L|+|E|) содержатся в наборе E,

Следующие |G| чисел (|L|+|E|+1 -> end) содержатся в наборе G,

Мы ищем kth Наименьшее число, поэтому у нас есть 3 случая:

1) k <= |L| это означает, что число, которое мы ищем, находится в первом |L| числа в отсортированном массиве, поэтому мы ищем kth наименьшее число в L,

2) |L| < k <= |L|+|E| это означает, что искомое число находится между (|L|+1 -> |L|+|E|) в отсортированном массиве, так что это элемент из E, Поскольку все элементы E равны xмы знаем, что kth наименьшее число равно x,

3) k > |L|+|E| это означает, что искомое число находится между (|L|+|E|+1 -> end) в отсортированном массиве, так что это элемент из "G". Так как уже есть |L|+|E| числа меньше, чем kth наименьшее число, мы можем вычесть |L|+|E| от kдавайте назовем это k' (k' = k - |L| - |E|) и искать k'th наименьший элемент в G,