Дан список неупорядоченных номеров с дубликатами и еще один список номеров с индексами. Найдите число, которое появляется в отсортированном порядке по данному индексу.
Мы должны рассматривать ввод только до точки индекса index массива, в котором мы находимся в настоящее время.
Если мы рассматриваем элемент 2 в массиве index, нам следует искать второй отсортированный элемент во входном массиве 3 7 9 10
I/P => 3 7 9 10 1 2
Index => 1 1 3 2 5 1
The output should be
3 3 9 7 10 1
Ex. элемент 5 в массиве Index будет иметь соответствующий отсортированный входной массив как 1 3 7 9 10, поэтому 5-й элемент - 10
Мое решение состояло в том, чтобы использовать multiset , а затем использовать advance, чтобы найти n-й индекс в наборе.
For i : [1 : len(I/P)]
set.add(I/P[i])
advance(I/P, Index[i])
print
Но заданная проблема не поддерживает произвольный доступ и advance ухудшается до линейного времени.
Как мне решить эту проблему в N Log(n)