Найдите последний положительный элемент, оставшийся после многократного вычитания наименьшего положительного элемента из всех элементов массива

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

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

Примеры:

Input: arr[] = {3, 5, 4, 7}
Output: 2
Explanation: 
Subtract the smallest positive element from the array, i.e. 3, the new array is arr[] = {0, 2, 1, 4}
Subtract the smallest positive element from the array, i.e. 1, the new array is arr[] = {0, 1, 0, 3}
Subtract the smallest positive element from the array, i.e. 1, the new array is arr[] = {0, 0, 0, 2}
The last remaining element is 2.

Input: arr[] = {2, 6, 7}
Output: 1

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

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

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

  • Если N = 1 , вывести первый элемент массива.
  • В противном случае выведите разницу между самым большим и вторым по величине элементом массива.

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

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

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