Найти все числа в диапазоне [1, N], которых нет в заданном массиве

Опубликовано: 21 Сентября, 2022

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

Примеры:

Input: arr[ ] = {5, 5, 4, 4, 2}
Output: 1 3
Explanation: 
For all numbers in the range [1, 5], 1 and 3 are not present in the array.

Input: arr[ ] = {3, 2, 3, 1}
Output: 4

Наивный подход. Самый простой подход — хешировать каждый элемент массива, используя любую структуру данных, такую как словарь, а затем перебирать диапазон [1, N] и печатать все числа, отсутствующие в хеше.

г

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

Подход: вышеприведенный подход можно дополнительно оптимизировать, пометив число в позиции arr[i] – 1 отрицательным, чтобы отметить, что i присутствует в массиве. Затем выведите все позиции элементов массива, которые положительны, поскольку они отсутствуют. Выполните следующие шаги, чтобы решить проблему:

  • Перебрать массив,arr[] и для каждого текущего элемента num выполнить следующие шаги:
    • Обновить arr[abs(num)-1] до -abs(arr[abs(num)-1]).
  • Перебрать массив, arr[] используя переменную i , и вывести i+1 , если arr[i] положительный.

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

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

РЕКОМЕНДУЕМЫЕ СТАТЬИ