Минимум удалений спереди или сзади, необходимый для удаления максимума и минимума из массива

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

Дан массив arr[] , состоящий из целых чисел. Задача состоит в том, чтобы найти минимальные удаления, необходимые для удаления начального минимального и максимального элемента из arr[] .
ПРИМЕЧАНИЕ. Удаление можно выполнить как спереди, так и сзади. массива.

Примеры:

Input: arr[] = {5, 7, 2, 4, 3}
Output: 3
Explanation: Initial minimum = 2, Initial maximum = 7
Deleting first 3 from arr[] updates arr[] to {2, 4, 3} which is free from Initial maximum and minimum elements.
Therefore 3 operations are required which is minimum possible.

Input: arr[] = {2, -1, 3, 5, 8, -7}
Output: 2

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

  • Инициализируйте две переменные, скажем, mn , mx для хранения минимального и максимального элементов соответственно.
  • Используйте две переменные, скажем , minIndex, maxIndex, чтобы сохранить последнее вхождение минимального и максимального элементов.
  • Итерировать arr[] с i
    • обновить мн = мин (мн, обр [я])
    • обновить mx = max (mx, обр [i])
  • Используйте две переменные, скажем, minIndex, maxIndex, чтобы сохранить последнее вхождение минимального и максимального элементов.
  • Итерировать arr[] с i
    • если arr[i] = mn , то обновить minIndex = i
    • если arr[i] = mx , то обновить maxIndex = i
  • Вычислите все случаи удаления и сохраните в переменных x, y, z .
  • Верните минимум среди x, y, z в качестве окончательного ответа.

Ниже приведена реализация описанного выше подхода.

Сложность времени: НА)

Вспомогательное пространство: О(1)

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