Дайте структуру данных, которую вы можете инициализировать в O (n), учитывая n пар ключей со значениями в [1, n ^ 3], и найдите все пары, где левое значение равно a в O (logn)

Question

Дайте структуру данных, которую вы можете инициализировать в O (n), учитывая n пар ключей со значениями в [1, n ^ 3], и найдите все пары, где левое значение равно a в O (logn) (сложность пространства должна бытьO (n))

Я получил эту проблему в курсе структур данных, первая часть была посвящена диапазону [1,10n] и O (1) для сложности поиска, которая была намного проще.Я попробовал несколько структур, но, кажется, ничего не работает в необходимой сложностиЕсли я просто вставлю все в массив, я не смогу получить то, что мне нужно, в O (logn), поэтому я не думаю, что это правильный путь.Деревья также, кажется, не полезны, так как они не могут инициализироваться в нужное время.

Буду очень признателен за правильное руководство, не дав ответа, если это возможно

Answer 1

Сортированный массив пар отлично работает. Поскольку значения <= n <sup>3 , вы можете использовать радикальную сортировку, чтобы отсортировать их по времени O (n) и пространству O (n). Найти все пары с определенным первым значением, вы можете выполнить два двоичных поиска, чтобы найти начальную и конечную позиции этого списка в массиве.