Как отсортировать группу из n объектов с O (n) временем и O (1) пространством. Каждый объект имеет два поля: int и string.

Question

Как отсортировать группу из n объектов. Каждый объект имеет два поля: int и string.

Объекты должны быть отсортированы в соответствии с полем int. Но мы знаем только диапазон поля int, а не его значение.

Это должно быть сделано за O (n) времени и O (1) пространства.

Я предлагаю сортировку ведром, но я не знаю, как это сделать с пробелом O (1).

Можно использовать быструю сортировку, но это O (n lg n).

Есть идеи? спасибо

Answer 1

Как только диапазон целых чисел фиксирован, массиву из одного сегмента для каждого значения в диапазоне требуется пробел O (1). Помните, что любое фиксированное пространство, не зависящее от экземпляра проблемы, равно O (1).

Полное решение предполагает произвольный доступ к выходным данным.

1. Мы начнем с подсчета частоты каждого входного целого числа (O (n) время, O (1) пробел)
2. Из частот мы можем вычислить первый выходной индекс для каждого входного целого числа в O (1) пробели время
3. Мы делаем второй проход по входу и сохраняем каждый элемент ввода в правильно упорядоченной позиции вывода.После сохранения одного элемента мы увеличиваем выходной индекс для целочисленного значения элемента.(O (n) время, O (1) пространство)

Общая сложность составляет O (n) время, O (1) пространство, как объявлено.

Я несм. решение, отвечающее требованиям, когда у нас нет вывода с произвольным доступом.

Answer 2

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