Найти все повторяющиеся и отсутствующие числа в заданном массиве перестановок от 1 до N

Дан массив arr[] размера N , состоящий из первых N натуральных чисел, задача состоит в том, чтобы найти все повторяющиеся и отсутствующие числа в диапазоне [1, N] в заданном массиве.

Примеры:

Input: arr[] = {1, 1, 2, 3, 3, 5}
Output: 
Missing Numbers: [4, 6]
Duplicate Numbers: [1, 3]
Explanation:
As 4 and 6 are not in arr[] Therefore they are missing and 1 is repeating two times and 3 is repeating two times so they are duplicate numbers. 

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

Подход: Данную проблему можно решить, используя идею, обсуждаемую в этой статье, когда повторяется только один элемент, а другой дублируется. Выполните следующие шаги, чтобы решить данную проблему:

• Инициализируйте массив, скажем, missing[] , в котором хранятся недостающие элементы.
• Инициализируйте набор, скажем, дубликат , в котором хранятся повторяющиеся элементы.
• Пройдите по заданному массиву arr[] с помощью переменной i и выполните следующие шаги:
  • Если значение arr[i] != arr[arr[i] – 1] истинно, то текущий элемент не равен тому месту, где он должен был бы находиться, если бы присутствовали все числа от 1 до N . Так что поменяйте местами arr[i] и arr[arr[i] – 1] .
  • В противном случае это означает, что тот же элемент присутствует в arr[arr[i] – 1] .
• Пройдите по заданному массиву arr[] с помощью переменной i , и если значение arr[i] не совпадает с (i + 1) , то отсутствующий элемент — (i + 1) , а повторяющийся элемент — arr[i] .
• После выполнения вышеуказанных шагов выведите в качестве результата элементы, сохраненные в Missing[] и Duplicate[] .

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

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