Dada una array arr[] de N enteros y un entero K , la tarea es encontrar el número mínimo de operaciones requeridas para ordenar la array en orden no decreciente de modo que en cada operación cualquier elemento de la array arr[i] pueda intercambiarse con K si el valor de (arr[i] > K) .
Ejemplos:
Entrada: arr[] = {0, 2, 3, 5, 4}, K = 1
Salida: 3
Explicación:
La array dada se puede ordenar siguiendo los siguientes pasos:
- Para i = 1, ya que arr[1] > K, intercambiando los valores de arr[1] y K. Por lo tanto, la array se convierte en {0, 1, 3, 5, 4} y el valor de K = 2.
- Para i = 2, ya que arr[2] > K, intercambiando los valores de arr[2] y K. Por lo tanto, la array se convierte en {0, 1, 2, 5, 4} y el valor de K = 3.
- Para i = 3, ya que arr[3] > K, intercambiando los valores de arr[3] y K. Por lo tanto, la array se convierte en {0, 1, 2, 3, 4} y el valor de K = 5.
Después de las operaciones anteriores, la array dada se ha ordenado.
Entrada: arr[] = {1, 3, 5, 9, 7}, K = 10
Salida: -1
Enfoque: El problema dado se puede resolver utilizando un enfoque codicioso , la idea es minimizar el valor de arr[i] en cada paso para todos los i en el rango [0, N – 1], que es la opción más óptima para el futuro . array a ordenar. Por lo tanto, si el valor de arr[i] > K , intercambiar los valores de arr[i] y K es la opción más óptima. Siga los pasos a continuación para resolver el problema dado:
- Cree una variable cnt , que almacene el recuento de las operaciones realizadas. Inicialmente cnt = 0 .
- Recorra la array arr[] usando una variable i en el rango [0, N-1] en orden creciente de i .
- Para cada índice, si arr[i] > K , intercambie el valor de K y arr[i] e incremente el valor de cnt en 1 .
- Después de cada operación, verifique si la array arr[] está ordenada o no usando el enfoque discutido en este artículo . Si la array arr[] está ordenada, devuelve el valor de cnt como la respuesta requerida.
- Si la array no se ordena después de realizar los pasos anteriores, la impresión -1 .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program of the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum number
// of given operations in order to sort
// the array arr[] in non-decreasing order
int minimumswaps(int arr[], int N, int K)
{
// If arr[] is already sorted, return 0
if (is_sorted(arr, arr + N)) {
return 0;
}
// Stores the count of operations
int cnt = 0;
// Loop to iterate over the array
for (int i = 0; i < N; i++) {
// If arr[i] is greater than K,
// minimize the value of arr[i]
if (arr[i] > K) {
swap(arr[i], K);
// Increment the count by 1
cnt++;
// Check if the array is sorted
// after the last operation
if (is_sorted(arr, arr + N)) {
// Return answer
return cnt;
}
}
}
// Not Possible to sort the array using
// given operation, hence return -1
return -1;
}
// Driver Code
int main()
{
int arr[] = { 0, 2, 3, 5, 4 };
int N = sizeof(arr) / sizeof(arr[0]);
int K = 1;
cout << minimumswaps(arr, N, K);
return 0;
}
Java
// Java program of the above approach
import java.io.*;
class GFG
{
static boolean is_sorted(int arr[], int N)
{
for (int i = 0; i < N - 1; i++)
{
if (arr[i] > arr[i + 1])
return false;
}
return true;
}
// Function to find the minimum number
// of given operations in order to sort
// the array arr[] in non-decreasing order
static int minimumswaps(int arr[], int N, int K)
{
// If arr[] is already sorted, return 0
if (is_sorted(arr, N)) {
return 0;
}
// Stores the count of operations
int cnt = 0;
// Loop to iterate over the array
for (int i = 0; i < N; i++) {
// If arr[i] is greater than K,
// minimize the value of arr[i]
if (arr[i] > K) {
int temp = arr[i];
arr[i] = K;
K = temp;
// Increment the count by 1
cnt++;
// Check if the array is sorted
// after the last operation
if (is_sorted(arr, N)) {
// Return answer
return cnt;
}
}
}
// Not Possible to sort the array using
// given operation, hence return -1
return -1;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 0, 2, 3, 5, 4 };
int N = arr.length;
int K = 1;
System.out.println(minimumswaps(arr, N, K));
}
}
// This code is contributed by Dharanendra L V.
Python3
# Python 3 program of the above approach def is_sort(arr): for i in range(len(arr)-1): if arr[i]>arr[i+1]: return False return True # Function to find the minimum number # of given operations in order to sort # the array arr[] in non-decreasing order def minimumswaps(arr, N, K): # If arr[] is already sorted, return 0 if is_sort(arr): return 0 # Stores the count of operations cnt = 0 # Loop to iterate over the array for i in range(N): # If arr[i] is greater than K, # minimize the value of arr[i] if(arr[i] > K): temp = arr[i] arr[i] = K K = temp # Increment the count by 1 cnt += 1 # Check if the array is sorted # after the last operation if is_sort(arr): # Return answer return cnt # Not Possible to sort the array using # given operation, hence return -1 return -1 # Driver Code if __name__ == '__main__': arr = [0, 2, 3, 5, 4] N = len(arr) K = 1 print(minimumswaps(arr, N, K)) # This code is contributed by bgangwar59.
C#
// C# program of the above approach
using System;
class GFG {
static bool is_sorted(int[] arr, int N)
{
for (int i = 0; i < N - 1; i++) {
if (arr[i] > arr[i + 1])
return false;
}
return true;
}
// Function to find the minimum number
// of given operations in order to sort
// the array arr[] in non-decreasing order
static int minimumswaps(int[] arr, int N, int K)
{
// If arr[] is already sorted, return 0
if (is_sorted(arr, N)) {
return 0;
}
// Stores the count of operations
int cnt = 0;
// Loop to iterate over the array
for (int i = 0; i < N; i++) {
// If arr[i] is greater than K,
// minimize the value of arr[i]
if (arr[i] > K) {
int temp = arr[i];
arr[i] = K;
K = temp;
// Increment the count by 1
cnt++;
// Check if the array is sorted
// after the last operation
if (is_sorted(arr, N)) {
// Return answer
return cnt;
}
}
}
// Not Possible to sort the array using
// given operation, hence return -1
return -1;
}
// Driver Code
public static void Main(string[] args)
{
int[] arr = { 0, 2, 3, 5, 4 };
int N = arr.Length;
int K = 1;
Console.WriteLine(minimumswaps(arr, N, K));
}
}
// This code is contributed by ukasp.
Javascript
<script>
// JavaScript Program to implement
// the above approach
function is_sorted(arr, N) {
for (let i = 0; i < N - 1; i++) {
if (arr[i] > arr[i + 1])
return false;
}
return true;
}
// Function to find the minimum number
// of given operations in order to sort
// the array arr[] in non-decreasing order
function minimumswaps(arr, N, K)
{
// If arr[] is already sorted, return 0
if (is_sorted(arr, N)) {
return 0;
}
// Stores the count of operations
let cnt = 0;
// Loop to iterate over the array
for (let i = 0; i < N; i++) {
// If arr[i] is greater than K,
// minimize the value of arr[i]
if (arr[i] > K) {
let temp = arr[i];
arr[i] = K;
K = temp;
// Increment the count by 1
cnt++;
// Check if the array is sorted
// after the last operation
if (is_sorted(arr, N)) {
// Return answer
return cnt;
}
}
}
// Not Possible to sort the array using
// given operation, hence return -1
return -1;
}
// Driver Code
let arr = [0, 2, 3, 5, 4];
let N = arr.length;
let K = 1;
document.write(minimumswaps(arr, N, K));
// This code is contributed by Potta Lokesh
</script>
Producción:
3
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)