N целых чисел для сортировки в O (n)?

Question

Предположим, у вас есть n целых чисел в диапазоне (0, n2 ). Эти целые числа являются квадратными корнями других целых чисел. Укажите, можно ли отсортировать эти числа в O (n) или нет

Я предполагаю, что мы бы взяли квадратные корни каждого из целых чисел, но я не уверен, что если их можно отсортировать по O (n), любая помощь будет принята

Answer 1

Да, если вы хотите использовать O (n) пробел:

• Вы сохранили N целых чисел в массиве A.
• Выделите битовую карту B с помощью 2n + 1биты, инициализированные в нуле.
• Для каждого целого числа установите B [A [i]] = 1
• Создайте пустой список:
• Итерируйте B по порядку, чтобыесли B [i] == 1, то i добавляется в список.

Это можно сделать за время O (2n) == O (n).