У меня проблемы с этим вопросом сортировки.Опишите алгоритм, который сортирует массив с условиями:
1.В отсортированном массиве есть 3 возможных различия (k1, k2, k3 все натуральные числа) между всеми соседними элементами.
2.В отсортированном массиве есть 3 возможных различия (k1, k2 = 2k1, k3 = 3k1 все рациональные числа) между всеми соседними элементами.
Мне удалось найти различия в обоих вопросах за линейное время O (n), но я застрял на O (nlogn) в части sotring.
Попытка, возможно, к O (n) время или, может быть, O (nloglogn), может быть, ссылаться на k1, k2, k3 как на действительно малые числа и использовать счетную сортировку.
Спасибо.