 Найти N меньших элементов множества M, как это можно сделать наиболее быстро? |
Здравствуйте, гость ( Вход | Регистрация )
ViGOur опции профиля:
|
 23.1.2012, 14:06
Сообщение
#1
|
 Мастер  Группа: Модератор Сообщений: 3296 Регистрация: 9.10.2007 Из: Москва Пользователь №: 4 Спасибо сказали: 231 раз(а) Репутация:  40 
 |
Собственно задача в названиии: Найти N меньших элементов множества M, нужен наиболее быстрый алгоритм поиска
M может быть как 100, так и стремиться к бесконечности!  В множестве только числа, от 0 до X. p.s. приводите свои варианты, не стесняйтесь! |
 |
  
|
 |
Ответов
|
Алексей1153 опции профиля:
|
23.1.2012, 16:26
Сообщение
#2
|
 фрилансер Группа: Участник Сообщений: 2943 Регистрация: 19.6.2010 Из: Обливион Пользователь №: 1822 Спасибо сказали: 215 раз(а) Репутация: 34
|
1) если исходные данные изначально хранить в индексированном виде, то всё элементарно
2) (скрыл спойлером) Раскрывающийся текст ага! Не подглядывай  если сортировка отпадает, то решение, по-моему, единственное: отсортированный массив результатов с максимальным размером N . Пробегая по исходным данным, нужно проверять, не оказался ли рассматриваемый элемент меньше всех, либо равный наименьшему в массиве результата. Если да - добавить его туда, выбросив самый большой элемент (сохраняя сортировку).и так , пока не всё (разумеется, в начале работы массив результатов пуст, потом по элементику растёт до N) Сообщение отредактировал Алексей1153 - 23.1.2012, 16:31 |
|
|
|
Сообщений в этой теме
ViGOur Найти N меньших элементов множества M 23.1.2012, 14:06
FantasyOr qSort
и берёшь N элементов с нужного края.
сделал ... 23.1.2012, 15:48 ViGOur По условию задачи количество элементов множества м... 23.1.2012, 16:02 wiz29 самый надежный способ пройти перебором по всем эле... 23.1.2012, 16:53 ViGOur Да, забыл сказать, что в множестве только числа, о... 23.1.2012, 16:56 wiz29 из вышеуказанной постановки, при M->∞ зад... 23.1.2012, 16:57 ViGOur А что оно тебе даст? Я понимаю, что в случае 0 ... 23.1.2012, 17:07 Алексей1153 ViGOur, я оговорился - не индексированные, а отсор... 23.1.2012, 19:54 ViGOur В таком случае будет потрачено кучу времени на сор... 23.1.2012, 22:11 Iron Bug дык, тебе уже написали: пройтись линейно по всему ... 23.1.2012, 23:24 ViGOur Iron Bug, я знаю ответ. Просто точный ответ, дал т... 24.1.2012, 7:24 wiz29 список из N сортированных элементов поддерживать э... 24.1.2012, 9:04 ViGOur Это не реальная задача, а чисто алгоритмическая, ч... 24.1.2012, 9:08 wiz29 алгоритм однопроходный с поддержанием в отсортиров... 24.1.2012, 10:29 cross Поправьте если я не прав, но разве поддержание отс... 24.1.2012, 12:40 igor_bogomolov ViGOur, так была уже такая тема. Ты же и создавал
... 24.1.2012, 13:10
ViGOur Ну наконец-то! И решение и вспомнили! 24.1.2012, 13:32 AD Цитата(ViGOur @ 24.1.2012, 14:32) Ну нако... 24.1.2012, 14:10 |
Теги
Нет тегов для показа
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0
|
|
Текстовая версия | Сейчас: 4.5.2025, 1:51 |