Алгоритм QuickSelect работает с дублирующимися значениями?
Если у меня есть массив
int[] array = {9, 8, 7, 6, 6, 6, 5, 0, 1, 2, 3, 4, 5, 5, 7, 200};
Сможет ли он получить k-й наименьший элемент, даже если есть дубликаты?
Да, это работает.К концу каждой итерации все элементы, меньшие текущей сводки, сохраняются слева от сводки.
Рассмотрим случай, когда все элементы одинаковы.В этом случае каждая итерация заканчивается размещением элемента pivot слева от массива.И следующая итерация будет продолжена с одним элементом более короткого массива.Поэтому нам нужно k итераций, чтобы найти k-й наименьший элемент.
k