Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 06.12.2010, 23:22
Новичок

Отправить личное сообщение для motz-art Посмотреть профиль Найти все сообщения от motz-art
 
Регистрация: 16.08.2009
Сообщений: 6

Поиск сечения колекции (медианы)
Есть колекция произвольных чисел А (несортированый, распределение неизвестно) нужно установить такое пороговое число 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

Очень желательно, что бы сложность алгоритма была линейной.
  #2  
Старый 07.12.2010, 00:12
гост

 
Сообщений: n/a

en.wikipedia.org/wiki/Selection_algorithm
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Построение сечения Mozilla Вычислительная геометрия 1 10.01.2008 00:29