Сортировка массива A в o (nlogn)

Question

Дан массив A целых чисел длины n.сортировать A по (small o) o (nlogn), когда в отсортированном массиве A каждые два последовательных элемента отличаются на k1, k2, k3, где k1, k2, k3

- это разные натуральные числа.

У меня возникла проблема с решением этого вопроса, я попытался найти минимум на A и создать три новых массива, каждый из которых начинается с min {A} длины n, образуя арифметическую последовательность в каждом массиве, используя k1, k2, k3.объединение результатов и удаление дублированных копий каждого элемента и, наконец, вырезание всех элементов после max {A} в новом отсортированном массиве длиной 3n.все операции O (n)

.

проблема в том, что это не работает, когда разница между max {A} −min {A} не делится ни на какие k1, k2,k3

.

любая помощь или понимание будет принята с благодарностью.

Answer 1

Создание ориентированного графа с номерами в массиве в качестве узлов.Для каждого числа x, если существует какой-либо из x + k1,k2,k3, добавьте направленное ребро.Теперь выполните простую топологическую сортировку.

Топологическая сортировка занимает O(V + E) время.Здесь V = n и E <= 3 * n.Итак, время топологической сортировки составляет O(n).Проверка существования x+k1,k2,k3 также может быть выполнена за линейное время с использованием хеш-таблицы.

Общая сложность времени: O(n).

Еще один способ решения проблемы:

Найдите наименьшее число в массиве.Пусть число будет х.Это первый элемент отсортированного массива.Теперь проверьте, существуют ли x+k1, x+k2 или x+k3 в массиве.По крайней мере один из них должен существовать в массиве в соответствии с заданным условием.Наименьшим из них является второй элемент отсортированного массива.Повторяйте эти шаги, пока у вас нет элементов.

Каждый шаг требует 3 запросов о существовании, и есть n шагов.С хэш-таблицей алгоритм будет линейным.

Answer 2

Вопрос неясен для меня, и поскольку я не могу комментировать для пояснения, я предполагаю два случая и отвечаю на оба сценария.

Сценарий 1: В вашем вопросе Сортировка означает то, что мы понимаем под сортировкой (по возрастанию или по убыванию):

В этом случае вам нечего делать, не проверяя, имеют ли последовательные элементы разность k1, k2 или k3.

Сценарий 2: В вашем вопросе Sorted означает перестановку заданных элементов массива таким образом, чтобы разница между последовательными элементами составляла k1, k2 или k3.

Пример: вход: [1, 2, 4, 5, 10], k1: 1, k2: 3, k3: 6

Выход: [1, 2, 5, 4, 10]

В этом случае это Гамильтонова задача поиска пути , и эту проблему можно решить с помощью DFS.Сначала построим граф из данного массива.Логика построения графика приведена ниже:

1. Каждый индекс является узлом
2. Два индекса (i, j) связаны, если abs (A [i] -A [j])k1, k2 или k3.

Следующим шагом является определение пути длины N со всеми N узлами в графе.

Сложность сценария 2:

Это NP-полная проблема.