Найти позицию ведущего элемента в заданном массиве с заданными операциями
Дан массив arr[] . Задача состоит в том, чтобы найти позицию ведущего элемента в arr[] . Лидирующий элемент — это тот, который может удалить все остальные элементы в массиве, используя следующие операции.
- Если arr[i] > arr[i + 1] , он удаляет (i+1) -й элемент и увеличивает его значение на 1 и уменьшает размер массива на 1 .
- Если arr[i] > arr[i – 1] , он удаляет (i-1) -й элемент и увеличивает его значение на 1 и уменьшает размер массива на 1 .
Примеры
Input: arr[] = { 5, 3, 4, 4, 5 }
Output: 3
Explanation: Following are the operations performed in array arr[]
A3 remove A2 and increment by 1 and array becomes { 5, 5, 4, 5 }
A2 remove A3 and increment by 1 and array becomes { 5, 6, 5 }
A2 remove A1 and increment by 1 and array becomes { 7, 5 }
A1 remove A2 and increment by 1 and array becomes { 8 }
Hence, The position of leader of array is 3.Input: arr[] = { 4, 4, 3, 4, 4 }
Output: 2
Explanation: Following are the operations performed in array arr[]
A2 remove A3 and increment by 1 and array becomes { 4, 5, 4, 4 }
A2 remove A1 and increment by 1 and array becomes { 6, 4, 4 }
A1 remove A2 and increment by 1 and array becomes { 7, 4 }
A1 remove A2 and increment by 1 and array becomes { 8 }
Hence, The position of leader of array is 2.Input: arr[] = { 1, 1, 1 }
Output: -1
Explanation: No leader is present in the array
Подход: Эта проблема основана на реализации. Выполните следующие шаги, чтобы решить данную проблему.
- Найдите максимальный и минимальный элементы массива arr .
- Если минимальный и максимальный элементы совпадают, это означает, что ведущий элемент отсутствует.
- Пройдитесь по массиву.
- Теперь проверьте, является ли arr[i] максимальным элементом.
- Проверьте , что arr[i-1] или arr[i+1] меньше max .
- Таким образом, этот элемент является ведущим элементом в массиве.
- Выведите позицию найденного элемента выноски.
Ниже приведена реализация описанного выше подхода.
Временная сложность: O(N)
Вспомогательное пространство: O(1)