Сгенерируйте перестановку первых N натуральных чисел, имеющую количество уникальных смежных разностей, равное K | Набор 2

Даны два натуральных числа N и K , задача состоит в том, чтобы построить перестановку первых N натуральных чисел так, чтобы все возможные абсолютные разности между соседними элементами были K .

Примеры:

Input: N = 3, K = 1
Output: 1 2 3
Explanation: Considering the permutation {1, 2, 3}, all possible unique absolute difference of adjacent elements is {1}. Since the count is 1(= K), print the sequence {1, 2, 3} as the resultant permutation.

Input: N = 3, K = 2
Output: 1 3 2

Наивный подход и двухуказательный подход к этой проблеме уже обсуждались здесь. В этой статье обсуждается другой подход к deque.

Подход: Легко видеть, что можно сгенерировать ответы для всех значений K между [1, N-1] . Для любого K вне этого диапазона ответа не существует. Чтобы решить эту проблему, поддерживайте двустороннюю очередь для всех текущих элементов и вектор для хранения последовательности. Кроме того, поддерживайте логическое значение, которое поможет определить, следует ли извлекать передний или задний элемент. Повторите оставшийся элемент, и если K больше 1 , нажмите элемент в соответствии с логическим значением и уменьшите K на 1 . Переверните логическое значение так, чтобы все оставшиеся различия имели значение 1 . Выполните следующие шаги, чтобы решить проблему:

• Если K больше, чем равно N или меньше 1, выведите -1 и верните результат, так как такой последовательности не существует.
• Инициализируйте двухстороннюю очередь dq[] для сохранения порядка элементов.
• Переберите диапазон [2, N], используя переменную i , и поместите i в конец deque dq[] .
• Инициализируйте фронт логической переменной как истину.
• Инициализируйте вектор ans[] для хранения ответа и поместите 1 в вектор ans[].
• Если K больше 1, то вычтите 1 из K и xor значение front с 1.
• Переберите диапазон [2, N], используя переменную i , и проверьте:
  • Если фронт равен 1 , затем извлеките переднюю часть двухсторонней очереди dq[] и поместите ее в вектор ans[] , в противном случае извлеките заднюю часть двухсторонней очереди dq[ ] и поместите ее в вектор ans[] . Кроме того, если K больше, тогда вычтите 1 из K и xor значение front с 1.
• Пройдите массив ans[] и распечатайте его элементы.

Ниже приведена реализация описанного выше подхода.

Временная сложность: O(N)
Вспомогательное пространство: O(N)