Лексикографически наименьшее число перестановок до K, имеющее заданный массив в качестве подпоследовательности

Для заданного целого числа K и массива arr[] с N попарно различными целыми числами в диапазоне [1, K] задача состоит в том, чтобы найти лексикографически наименьшую перестановку первых K положительных целых чисел, такую, что данный массив arr[] является подпоследовательностью перестановки.

Примеры:

Input: arr[] = {1, 3, 5, 7}, K = 8
Output: 1 2 3 4 5 6 7 8
Explanation: {1, 2, 3, 4, 5, 6, 7, 8} is the lexicographically smallest permutation of the first 8 positive integers such that the given array  {1, 3, 5, 7} is also a subsequence of the permutation.

Input: arr[] = {6, 4, 2, 1}, K=7
Output: 3 5 6 4 2 1 7

Подход: Данная проблема может быть решена с использованием жадного подхода. Ниже приведены шаги, которые необходимо выполнить:

• Создайте векторmissing[] , который хранит целые числа в диапазоне [1, K] в порядке возрастания, которых нет в данном массиве arr[] , используя подход, обсуждаемый в этой статье.
• Создайте два указателя p1 и p2 , которые сохраняют текущий индекс в arr[] иmissing[] соответственно. Изначально оба равны 0 .
• Жадно возьмите и сохраните минимум arr[p1] и недостающего [p2] в вектор, скажем, ans[] и увеличивайте соответствующий указатель на следующую позицию, пока количество сохраненных целых чисел не станет меньше K .
• Чтобы упростить задачу, добавьте INT_MAX в конец массиваmissing [] и arr[] , что позволит избежать выхода за границы.
• После выполнения вышеуказанных шагов все значения, хранящиеся в ответе [] , являются требуемым результатом.

Ниже приведена реализация вышеуказанного подхода:

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