|
Поиск сечения колекции (медианы)
Есть колекция произвольных чисел А (несортированый, распределение неизвестно) нужно установить такое пороговое число x которое разделяет значения на два подмножества с количествами елементов в каждом в заданных пропорциях.
A.where( i < x ).count() * k = A.where( i >= x ).count()
Пример.
Для:
A = [1,3,2,9,0,8,4,6,7,5]
k = 3;
Решение:
x = 2.5
Очень желательно, что бы сложность алгоритма была линейной.
|
Линейный вид
