#python #mapping #intervals
Вопрос:
Я пытаюсь создать отображение, где нам дается integer n , а также множество интервалов, которые сопоставляются со случайными числами.
например, n = 55, и скажем, что у нас есть интервалы: [1:3]-gt;-2,[4:10]-gt;-3,[11:25]-gt;-4,[26:44]-gt;-5,[45:66]-gt;-6, etc.
Возможно ли/как я могу создать отображение с постоянным временем, чтобы для любого заданного n я мог найти соответствующий интервал, а затем правильное отображение на отрицательное число?
Мои мысли состоят в том, чтобы создать словарь с ключами в качестве интервалов и значениями в качестве отрицательного числа — однако будет ли это поиск по постоянному времени для любого заданного n?
Комментарии:
1. что вы знаете о n? что вы знаете об интервалах?
2. Что вы подразумеваете под «правильным отображением на отрицательное число»? Вы хотите взять целое число, а затем найти значение, в котором целое число находится в диапазоне?
3. Извините, если я не был самым ясным, n-это целое число, которое попадает ровно в один из интервалов
4. Поэтому, следуя примеру, если n=27, я хочу, чтобы функция возвращала -5. Равно n=2, то я хочу, чтобы функция возвращала -2
5. Если
nограничено конечным числом значений и их удобно хранить в памяти, то диктант с каждым значением будет постоянным поиском по времени. Или если до 66 у вас есть приведенное выше отображение, а для n gt; 66 у вас, скажем, -7. Это также будет работать с диктом, используя значение по умолчанию для любых отсутствующих ключей. Список может достичь всего этого там, где вы сначала проверяете этоn lt; len(list_of_values), а затем извлекаете по индексу. Если нецелесообразно хранить все отображение целиком, то вы можете использовать пороговые значения деления пополам, но со сложностью O(logn).
Ответ №1:
Наивным решением было бы создать массив размера n и для каждого индекса инициализировать его целевым значением. Это расточительно (например, если n действительно велико, и у вас есть только один интервал). Построение массива выполняется O(n) вовремя, но доступ к массиву по индексу выполняется O(1) .
РЕДАКТИРОВАТЬ: Если количество заданных интервалов является константой, а не функцией от n, то повторение интервалов для поиска правильного может быть выполнено O(1) вовремя. В этом случае вам не нужно никаких dict или array .