Блог

Главная - Вопросы по программированию - найти частоту появления int в списке интервалов

найти частоту появления int в списке интервалов

#python #optimization #time-complexity

#python #оптимизация #временная сложность

Вопрос:

Мне был предоставлен список интервалов, например [[10,40],[20,60]] и список позиций [5,15,30] мы должны вернуть частоту появления позиции в списке, ответ будет [[5,0],[15,1],[30,2]] потому что 5 этого не сделалпокрытие интервалом и 15 было покрыто один раз, 30 было покрыто дважды. Если я просто выполню цикл for, временная сложность будет O (m * n) m — номер интервала, n — номер позиции. Могу ли я предварительно обработать интервалы и ускорить его? Я думал сначала отсортировать интервал и использовать двоичный поиск, но я не уверен, как это реализовать на python, может кто-нибудь дать мне подсказку? Или я могу использовать хеш-таблицу для хранения интервалов? какова будет временная сложность для этого?

Комментарии:

1. Похоже, вы могли бы создать структуру данных, которая хранится в виде последовательности неперекрывающихся диапазонов, связанных с частотами. Используйте двоичный поиск, чтобы найти диапазон для заданной «позиции» или интегрировать новый диапазон в структуру, и это должно привести к тому, что обе операции войдут в журнал (m), так что в итоге вы получите (m n) log (m), чтобы построить структуру из интервалов, а затем запроситьсписок позиций.

2. хм, не совсем mlog (m) для его построения, поскольку вам нужно перебирать перекрывающиеся диапазоны для их интеграции, но вы поняли идею.

Ответ №1:

Вы можете использовать частотный массив для предварительной обработки всех данных интервала, а затем запросить любое значение, чтобы получить ответ. В частности, создайте массив, способный содержать минимальные и максимальные возможные конечные точки всех интервалов. Затем для каждого интервала увеличивайте частоту начальной точки интервала и уменьшайте частоту значения сразу после конечного интервала. В конце соберите эти данные для массива, и у нас будет частота появления каждого значения между минимальным и максимальным интервалом. Затем каждый запрос просто возвращает значение частоты из этого массива.

  1. freq[] —> больше max-min 1 (min: минимальное начальное значение, max: максимальное конечное значение)
  2. Для каждого [L, R] —> freq[L] , freq[R 1] = freq[R 1] -1
  3. freq[i] = freq[i] freq[i-1]
  4. Для любого запроса V ответом будет freq[V]

Учитывайте компромиссы, когда диапазон очень велик по сравнению с простыми запросами, где может быть достаточно простой проверки для всех.