Минимизируйте операции для сортировки заданного массива, поменяв местами K и arr[i], если K больше

Учитывая массив arr[] из N целых чисел и целое число K , задача состоит в том, чтобы найти минимальное количество операций, необходимых для сортировки массива в неубывающем порядке, так что в каждой операции любой элемент массива arr[i] можно поменять местами с K , если значение (arr[i] > K) .

Примеры:

Input: arr[] = {0, 2, 3, 5, 4}, K = 1
Output: 3 
Explanation:
The given array can be sorted using the following steps:

1. For i = 1, since arr[1] > K, swapping the values of arr[1] and K. Hence, the array becomes {0, 1, 3, 5, 4} and value of K = 2.
2. For i = 2, since arr[2] > K, swapping the values of arr[2] and K. Hence, the array becomes {0, 1, 2, 5, 4} and value of K = 3.
3. For i = 3, since arr[3] > K, swapping the values of arr[3] and K. Hence, the array becomes {0, 1, 2, 3, 4} and value of K = 5.

After the above operations, the given array has been sorted.
 

Input: arr[] = {1, 3, 5, 9, 7}, K = 10
Output: -1

 

Подход: данная задача может быть решена с помощью жадного подхода, идея состоит в том, чтобы минимизировать значение arr[i] на каждом шаге для всех i в диапазоне [0, N – 1] , что является наиболее оптимальным выбором для дальнейшего массив для сортировки. Следовательно, если значение arr[i] > K , замена значений arr[i] и K является наиболее оптимальным выбором. Выполните следующие шаги, чтобы решить данную проблему:

• Создайте переменную cnt , в которой хранится количество выполненных операций. Первоначально cnt = 0 .
• Пройдите массив arr[] , используя переменную i в диапазоне [0, N-1] в порядке возрастания i .
• Для каждого индекса, если arr[i] > K , поменяйте местами значения K и arr[i] и увеличьте значение cnt на 1 .
• После каждой операции проверяйте, отсортирован ли массив arr[] , используя подход, обсуждаемый в этой статье. Если массив arr[] отсортирован, вернуть значение cnt в качестве требуемого ответа.
• Если массив не отсортирован после выполнения вышеуказанных шагов, выводится -1 .

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

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