Минимизируйте X так, чтобы массив можно было сделать 0, уменьшив элементы меньше, чем X
Дан массив A[] размера N . На каждом шаге уменьшайте элемент до 0 и уменьшайте все ненулевые элементы на 1, пока все элементы не станут 0. Найдите минимально возможное значение X , такое, чтобы массив можно было сделать 0, удалив значения, меньшие или равные X в каждый шаг.
Примеры:
Input: N = 4, A = {7, 18, 16, 14}
Output: 15
Explanation: At the beginning of the operation, the array has {7, 18, 16, 14}
Make 1st element 0, remaining array elements {0, 17, 15, 13}
Make 3rd element 0, remaining array elements {0, 16, 0, 12}
Make 4th element 0, remaining array elements {0, 15, 0, 0}
Make 2nd element 0, remaining array elements {0, 0, 0, 0}
Therefore the minimum value of X needs to be 15 units.Input: N = 1, A = {3}
Output: 3
Explanation: X has to be 3
Подход: Эту проблему можно решить с помощью жадного алгоритма .
Make the smallest element 0 first so that all the greater elements are reduced by 1 so that X can be minimized.
Следуйте шагам, указанным ниже, чтобы реализовать идею:
- Отсортируйте заданный массив.
- Начните создавать элементы 0, начиная с самого маленького элемента.
- Следовательно, для каждого i-го элемента массива значение в этот момент уменьшилось бы на i единиц, т.е. value = A[i] – i .
- Найдите максимальное значение среди A[i] – i , чтобы все элементы стали равными 0.
Ниже приведена реализация описанного выше подхода.
Временная сложность: O(N * log N)
Вспомогательное пространство: O(1)