0 / 0 / 1
Регистрация: 27.12.2012
Сообщений: 47
|
|
1 | |
Подскажите быстрый поиск количества интервалов в отрезке31.07.2013, 15:39. Показов 836. Ответов 6
Метки нет (Все метки)
Есть массив H[N]
Есть отрезок x+dx. Задача найти количество интервалов на которое делится отрезок x+dx массивом H[N]. Наверняка с такой задачей уже кучу раз сталкивались, и есть оптимальное по быстродействию решение. Подскажите его, а то у меня как то коряво получается.
0
|
31.07.2013, 15:39 | |
Ответы с готовыми решениями:
6
Поиск на отрезке количества чисел, сумма цифр которых есть однозначное число Поиск интервалов Поиск интервалов Поиск межбуквенных интервалов |
249 / 219 / 63
Регистрация: 30.07.2013
Сообщений: 465
|
|
31.07.2013, 15:54 | 2 |
1) пройтись по H[N], отобрать точки, попадающие в заданный отрезок. Время O(N).
2) отсортировать оторанные точки. Время O(NlogN). 3) удалить дубликаты в отсортированных точках. Время O(N). 4) число оставшихся отобранных точек + 1. Время O(1)
0
|
0 / 0 / 1
Регистрация: 27.12.2012
Сообщений: 47
|
||||||
31.07.2013, 16:15 [ТС] | 3 | |||||
Небольшое уточнение H[N] уже отсортирован...
Ну у меня вот как то так получается...Проверею конец и начало отрезка на предмет попадания в массив, далее нахожу конец и начало фрагмента в массиве.Норм? Кликните здесь для просмотра всего текста
0
|
249 / 219 / 63
Регистрация: 30.07.2013
Сообщений: 465
|
|
31.07.2013, 16:25 | 4 |
Дубликаты, я так, понимаю, тоже не встречаются. Ну тогда ок.
Но ведь это C++, есть множество готовых алгоримов в STL, включая двоичный поиск в отсортированном массиве. Если же главная задача - реализовать такой поиск руками, то хоть название функциям давайте осмысленные и соответствующие их задачам.
0
|
0 / 0 / 1
Регистрация: 27.12.2012
Сообщений: 47
|
|
01.08.2013, 10:47 [ТС] | 5 |
Да, там все таки есть дубликаты.
0
|
194 / 174 / 30
Регистрация: 10.07.2012
Сообщений: 800
|
|
01.08.2013, 10:52 | 6 |
1
|
0 / 0 / 1
Регистрация: 27.12.2012
Сообщений: 47
|
|
01.08.2013, 13:11 [ТС] | 7 |
выделил в отдельный топик.
Выделить из упорядоченного массива подмассив ограниченный точками x1, x2
0
|
01.08.2013, 13:11 | |
01.08.2013, 13:11 | |
Помогаю со студенческими работами здесь
7
Быстрый подсчет количества бит Быстрый подсчёт количества выставленных бит Поиск интервалов в которые входит заданная точка Хранение большого количества файлов и быстрый доступ к ним Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |