Найдите последний положительный элемент, оставшийся после многократного вычитания наименьшего положительного элемента из всех элементов массива
Дан массив 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)