Учитывая бесконечно большой массив с приоритетом, связанным с каждым элементом, затем сортируйте данный массив в соответствии с возрастающим приоритетом в O (n)

Question

Мне задали этот вопрос в интервью.Я не мог сделать лучше, чем O (NlogN).Я сортировал каждый раз.

Answer 1

Счетная сортировка или Радикальная сортировка может использоваться здесь, если требуется более быстрый алгоритм, чем O(nlogn).Вы можете достигнуть O(n) временной сложности (для сортировки Radix, она немного больше, чем постоянное время) с дополнительным пространством - O(n).