Minimice los intercambios necesarios para maximizar la cantidad de elementos que reemplazan un elemento mayor en una array

Dada una array A[] , que consta de N elementos, la tarea es encontrar el número mínimo de intercambios necesarios para que los elementos de la array intercambiados para reemplazar un elemento superior, en la array original, se maximicen.

Ejemplos:

Entrada: A[] = {4, 3, 3, 2, 5} 
Salida: 3 
Explicación: 
Intercambio 1: { 4 , 3, 3, 2, 5 } -> { 5 , 3, 3, 2, 4 } 
Intercambio 2: { 5 , 3, 3 , 2, 4} -> { 3 , 3, 5 , 2, 4} 
Intercambiar 3: {3, 3, 5 , 2 , 4} -> {3, 3, 2 , 5 , 4} 
Por lo tanto, los elementos {4, 3, 2} ocupan la posición original de un elemento superior después de intercambiar
Entrada: . A[] = {6, 5, 4, 3, 2, 1} 
Salida: 5

Enfoque ingenuo: el enfoque más simple para resolver el problema se puede implementar de la siguiente manera:

• Ordene la array en orden ascendente.
• Inicialice dos variables, resultado e índice , para almacenar el conteo y el índice hasta el cual se ha considerado en la array original, respectivamente.
• Iterar sobre los elementos de la array. Para cualquier elemento A[i] , vaya a un valor en la array que sea mayor que _ai e incremente la variable de índice en consecuencia.
• Después de encontrar un elemento mayor que A[i] , incremente el resultado y el índice .
• Si el índice ha llegado al final de la array, no quedan elementos para intercambiar con elementos previamente marcados.
• Por lo tanto, imprima la cuenta .

A continuación se muestra la implementación del enfoque anterior: 

// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the minimum
// number of swaps required
int countSwaps(int A[], int n)
{
    // Sort the array in ascending order
    sort(A, A + n);
 
    int ind = 1, res = 0;
 
    for (int i = 0; i < n; i++) {
 
        // Iterate until a greater element
        // is found
        while (ind < n and A[ind] == A[i])
 
            // Keep incrementing ind
            ind++;
 
        // If a greater element is found
        if (ind < n and A[ind] > A[i]) {
 
            // Increase count of swap
            res++;
 
            // Increment ind
            ind++;
        }
 
        // If end of array is reached
        if (ind >= n)
            break;
    }
 
    // Return the answer
    return res;
}
 
// Driver Code
int main()
{
 
    int A[] = { 4, 3, 3, 2, 5 };
    cout << countSwaps(A, 5);
 
    return 0;
}

// Java Program to implement
// the above approach
import java.util.*;
class GFG{
 
// Function to find the minimum
// number of swaps required
static int countSwaps(int A[], int n)
{
    // Sort the array in ascending order
    Arrays.sort(A);
    int ind = 1, res = 0;
 
    for (int i = 0; i < n; i++)
    {
 
        // Iterate until a greater element
        // is found
        while (ind < n && A[ind] == A[i])
 
            // Keep incrementing ind
            ind++;
 
        // If a greater element is found
        if (ind < n && A[ind] > A[i])
        {
 
            // Increase count of swap
            res++;
 
            // Increment ind
            ind++;
        }
 
        // If end of array is reached
        if (ind >= n)
            break;
    }
 
    // Return the answer
    return res;
}
 
// Driver Code
public static void main(String[] args)
{
    int A[] = { 4, 3, 3, 2, 5 };
    System.out.print(countSwaps(A, 5));
}
}
 
// This code is contributed by gauravrajput1

# Python3 program to implement
# the above approach
 
# Function to find the minimum
# number of swaps required
def countSwaps(A, n):
 
    # Sort the array in ascending order
    A.sort()
 
    ind, res = 1, 0
 
    for i in range(n):
 
        # Iterate until a greater element
        # is found
        while (ind < n and A[ind] == A[i]):
 
            # Keep incrementing ind
            ind += 1
 
        # If a greater element is found
        if (ind < n and A[ind] > A[i]):
 
            # Increase count of swap
            res += 1
 
            # Increment ind
            ind += 1
 
        # If end of array is reached
        if (ind >= n):
            break
 
    # Return the answer
    return res
 
# Driver Code
A = [ 4, 3, 3, 2, 5 ]
 
print (countSwaps(A, 5))
 
# This code is contributed by chitranayal

// C# Program to implement
// the above approach
using System;
class GFG{
 
// Function to find the minimum
// number of swaps required
static int countSwaps(int []A, int n)
{
    // Sort the array in ascending order
    Array.Sort(A);
    int ind = 1, res = 0;
 
    for (int i = 0; i < n; i++)
    {
 
        // Iterate until a greater element
        // is found
        while (ind < n && A[ind] == A[i])
 
            // Keep incrementing ind
            ind++;
 
        // If a greater element is found
        if (ind < n && A[ind] > A[i])
        {
 
            // Increase count of swap
            res++;
 
            // Increment ind
            ind++;
        }
 
        // If end of array is reached
        if (ind >= n)
            break;
    }
 
    // Return the answer
    return res;
}
 
// Driver Code
public static void Main(String[] args)
{
    int []A = { 4, 3, 3, 2, 5 };
    Console.Write(countSwaps(A, 5));
}
}
 
// This code is contributed by Amit Katiyar

<script>
// JavaScript program for the above approach
 
// Function to find the minimum
// number of swaps required
function countSwaps(A, n)
{
    // Sort the array in ascending order
    A.sort();
    let ind = 1, res = 0;
  
    for (let i = 0; i < n; i++)
    {
  
        // Iterate until a greater element
        // is found
        while (ind < n && A[ind] == A[i])
  
            // Keep incrementing ind
            ind++;
  
        // If a greater element is found
        if (ind < n && A[ind] > A[i])
        {
  
            // Increase count of swap
            res++;
  
            // Increment ind
            ind++;
        }
  
        // If end of array is reached
        if (ind >= n)
            break;
    }
  
    // Return the answer
    return res;
}
     
// Driver Code
 
    let A = [ 4, 3, 3, 2, 5 ];
    document.write(countSwaps(A, 5));
              
</script>

3

Complejidad de tiempo: O(N * log N) 
Espacio auxiliar: O(1)

Enfoque eficiente: 
dado que cualquier intercambio entre dos elementos desiguales lleva a que un elemento reemplace a un elemento superior, se puede observar que el número mínimo de intercambios requeridos es N – (la frecuencia máxima de un elemento de array) . Por lo tanto, encuentre el elemento más frecuente en la array utilizando HashMap e imprima el resultado.

A continuación se muestra la implementación del enfoque anterior: 

// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the minimum
// number of swaps required
int countSwaps(int A[], int n)
{
    // Stores the frequency of the
    // array elements
    map<int, int> mp;
 
    // Stores maximum frequency
    int max_frequency = 0;
 
    // Find the max frequency
    for (int i = 0; i < n; i++) {
 
        // Update frequency
        mp[A[i]]++;
 
        // Update maximum frequency
        max_frequency
            = max(max_frequency, mp[A[i]]);
    }
 
    return n - max_frequency;
}
 
// Driver Code
int main()
{
 
    int A[] = { 6, 5, 4, 3, 2, 1 };
 
    // function call
    cout << countSwaps(A, 6);
 
    return 0;
}

// Java Program to implement
// the above approach
import java.util.*;
class GFG{
 
// Function to find the minimum
// number of swaps required
static int countSwaps(int arr[], int n)
{
    // Stores the frequency of the
    // array elements
    HashMap<Integer,
              Integer> mp = new HashMap<Integer,
                                        Integer>();
 
    // Stores maximum frequency
    int max_frequency = 0;
 
    // Find the max frequency
    for (int i = 0; i < n; i++)
    {
 
        // Update frequency
        if(mp.containsKey(arr[i]))
        {
            mp.put(arr[i], mp.get(arr[i]) + 1);
        }
        else
        {
            mp.put(arr[i], 1);
        }
 
        // Update maximum frequency
        max_frequency = Math.max(max_frequency,
                                 mp.get(arr[i]));
    }
    return n - max_frequency;
}
 
// Driver Code
public static void main(String[] args)
{
    int A[] = { 6, 5, 4, 3, 2, 1 };
 
    // function call
    System.out.print(countSwaps(A, 6));
}
}
 
// This code is contributed by Rohit_ranjan

# Python3 Program to implement
# the above approach
 
# Function to find the minimum
# number of swaps required
def countSwaps(A, n):
     
    # Stores the frequency of the
    # array elements
    mp = {}
 
    # Stores maximum frequency
    max_frequency = 0
 
    # Find the max frequency
    for i in range(n):
 
        # Update frequency
        if A[i] in mp:
            mp[A[i]] += 1
        else:
            mp[A[i]] = 1
 
        # Update maximum frequency
        max_frequency = max(max_frequency,
                            mp[A[i]])
 
    return n - max_frequency
   
# Driver code
if __name__ == "__main__":   
 
      A = [6, 5, 4, 3, 2, 1]
     
    # function call
    print(countSwaps(A, 6))
 
# This code is contributed by divyeshrabadiya07

// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to find the minimum
// number of swaps required
static int countSwaps(int []arr, int n)
{
     
    // Stores the frequency of the
    // array elements
    Dictionary<int,
               int> mp = new Dictionary<int,
                                        int>();
 
    // Stores maximum frequency
    int max_frequency = 0;
 
    // Find the max frequency
    for(int i = 0; i < n; i++)
    {
         
        // Update frequency
        if(mp.ContainsKey(arr[i]))
        {
            mp[arr[i]] = mp[arr[i]] + 1;
        }
        else
        {
            mp.Add(arr[i], 1);
        }
 
        // Update maximum frequency
        max_frequency = Math.Max(max_frequency,
                                 mp[arr[i]]);
    }
    return n - max_frequency;
}
 
// Driver Code
public static void Main(String[] args)
{
    int []A = { 6, 5, 4, 3, 2, 1 };
 
    // Function call
    Console.Write(countSwaps(A, 6));
}
}
 
// This code is contributed by 29AjayKumar

<script>
 
// Javascript Program to implement
// the above approach
 
// Function to find the minimum
// number of swaps required
function countSwaps(A, n)
{
    // Stores the frequency of the
    // array elements
    var mp = new Map();
 
    // Stores maximum frequency
    var max_frequency = 0;
 
    // Find the max frequency
    for (var i = 0; i < n; i++) {
 
        // Update frequency
        if(mp.has(A[i]))
            mp.set(A[i], mp.get(A[i])+1)
        else
            mp.set(A[i], 1);
 
        // Update maximum frequency
        max_frequency
            = Math.max(max_frequency, mp.get(A[i]));
    }
 
    return n - max_frequency;
}
 
// Driver Code
var A = [6, 5, 4, 3, 2, 1 ];
// function call
document.write( countSwaps(A, 6));
 
</script>   

5

Complejidad temporal: O(N) 
Espacio auxiliar: O(N)