Minimice el recuento de intercambios de filas adyacentes para convertir la array dada en una array triangular inferior

Dada una array , mat[][] de tamaño N × N , la tarea es minimizar el recuento de intercambios de filas adyacentes para convertir la array dada en una array triangular inferior . Si no es posible convertir la array dada en una array triangular inferior, imprima -1. 
Nota: Una array triangular inferior contiene ceros en todos los índices por encima de la diagonal principal.

Ejemplos:

Entrada: mat[][] = {{0, 0, 2}, {3, 1, 0}, {4, 0, 0}}
Salida: 3
Explicación:  
Intercambiar la primera fila y la segunda fila {{3, 1, 0}, {0, 0, 2}, {4, 0, 0}}
Intercambiar fila 2 y 3 {{3, 1, 0}, {4, 0, 0}, {0, 0, 2}}
Intercambie la primera fila y la segunda fila {{4, 0, 0}, {3, 1, 0}, {0, 0, 2}}
Por lo tanto, la salida requerida es 3.

Entrada: mat[][] = {{0, 2, 3, 0}, {0, 2, 4, 0}, {0, 5, 1, 0}, {0, 1, 1, 0}}
Salida : -1

Planteamiento: Este problema se puede resolver usando la técnica Greedy . La idea de encontrar primero el recuento de ceros presentes en cada fila y almacenarlo en una array de enteros. Luego, cuente la cantidad mínima de intercambios adyacentes necesarios para ordenar la array en función de la cantidad de 0 en orden descendente. Siga los pasos a continuación para resolver el problema:

1. Inicialice una array, diga cntZero[] para almacenar el recuento de 0 s presentes en cada fila.
2. Para la fila i , recorra la array ^cntZero [] desde (i + 1) el índice y encuentre el primer índice, diga First donde ^ctnZero [First] >= (N – i -1) .
3. Intercambie todos los elementos adyacentes del i ^-ésimo índice al primer índice de la array cntZero[] e incremente el conteo.
4. Finalmente, devuelva el recuento de intercambios adyacentes necesarios para convertir la array dada en la array triangular inferior.

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 count the minimum
// number of  adjacent swaps
int minAdjSwaps(vector<vector<int> >& mat)
{
    // Stores the size of
    // the given matrix
    int N = mat.size();
 
    // Stores the count of zero
    // at the end of each row
    vector<int> cntZero(N, 0);
 
    // Traverse the given matrix
    for (int i = 0; i < N; i++) {
 
        // Count of 0s at the end
        // of the ith row
        for (int j = N - 1;
             j >= 0 && mat[i][j] == 0;
             j--) {
            cntZero[i]++;
        }
    }
 
    // Stores the count of swaps
    int cntSwaps = 0;
 
    // Traverse the cntZero array
    for (int i = 0; i < N; i++) {
 
        // If count of zero in the
        // i-th row < (N - i - 1)
        if (cntZero[i]
            < (N - i - 1)) {
 
            // Stores the index of the row
            // where count of zero > (N-i-1)
            int First = i;
            while (First < N
                   && cntZero[First]
                          < (N - i - 1)) {
                First++;
            }
 
            // If no row found that
            // satisfy the condition
            if (First == N) {
                return -1;
            }
 
            // Swap the adjacent row
            while (First > i) {
                swap(cntZero[First],
                     cntZero[First - 1]);
                First--;
                cntSwaps++;
            }
        }
    }
    return cntSwaps;
}
 
// Driver Code
int main()
{
    vector<vector<int> > mat
        = { { 0, 0, 2 },
            { 3, 1, 0 },
            { 4, 0, 0 } };
    cout << minAdjSwaps(mat);
}

// Java program to implement
// the above approach
import java.util.*;
 
class GFG{
 
// Function to count the minimum
// number of  adjacent swaps
static int minAdjSwaps(int [][]mat)
{
     
    // Stores the size of
    // the given matrix
    int N = mat.length;
 
    // Stores the count of zero
    // at the end of each row
    int []cntZero = new int[N];
 
    // Traverse the given matrix
    for(int i = 0; i < N; i++)
    {
         
        // Count of 0s at the end
        // of the ith row
        for(int j = N - 1;
                j >= 0 && mat[i][j] == 0;
                j--)
        {
            cntZero[i]++;
        }
    }
 
    // Stores the count of swaps
    int cntSwaps = 0;
 
    // Traverse the cntZero array
    for(int i = 0; i < N; i++)
    {
         
        // If count of zero in the
        // i-th row < (N - i - 1)
        if (cntZero[i] < (N - i - 1))
        {
             
            // Stores the index of the row
            // where count of zero > (N-i-1)
            int First = i;
            while (First < N && cntZero[First] <
                  (N - i - 1))
            {
                First++;
            }
 
            // If no row found that
            // satisfy the condition
            if (First == N)
            {
                return -1;
            }
 
            // Swap the adjacent row
            while (First > i)
            {
                cntZero = swap(cntZero, First,
                               First - 1);
                First--;
                cntSwaps++;
            }
        }
    }
    return cntSwaps;
}
 
static int[] swap(int []arr, int i, int j)
{
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
    return arr;
}
 
// Driver Code
public static void main(String[] args)
{
    int [][]mat = { { 0, 0, 2 },
                    { 3, 1, 0 },
                    { 4, 0, 0 } };
                     
    System.out.print(minAdjSwaps(mat));
}
}
 
// This code is contributed by Amit Katiyar

# Python3 program to implement
# the above approach
 
# Function to count the minimum
# number of  adjacent swaps
def minAdjSwaps(mat):
     
    # Stores the size of
    # the given matrix
    N = len(mat)
 
    # Stores the count of zero
    # at the end of each row
    cntZero = [0] * (N)
 
    # Traverse the given matrix
    for i in range(N):
 
        # Count of 0s at the end
        # of the ith row
        for j in range(N - 1, -1, -1):
            if mat[i][j] != 0:
                break
             
            cntZero[i] += 1
 
    # Stores the count of swaps
    cntSwaps = 0
 
    # Traverse the cntZero array
    for i in range(N):
 
        # If count of zero in the
        # i-th row < (N - i - 1)
        if (cntZero[i] < (N - i - 1)):
 
            # Stores the index of the row
            # where count of zero > (N-i-1)
            First = i
             
            while (First < N and
           cntZero[First] < (N - i - 1)):
                First += 1
 
            # If no row found that
            # satisfy the condition
            if (First == N):
                return -1
 
            # Swap the adjacent row
            while (First > i):
                cntZero[First] = cntZero[First - 1]
                cntZero[First - 1] = cntZero[First]
                 
                First -= 1
                cntSwaps += 1
                 
    return cntSwaps
 
# Driver Code
if __name__ == '__main__':
     
    mat = [ [ 0, 0, 2 ],
            [ 3, 1, 0 ],
            [ 4, 0, 0 ] ]
             
    print(minAdjSwaps(mat))
 
# This code is contributed by mohit kumar 29

// C# program to implement
// the above approach
using System;
class GFG{
 
// Function to count the minimum
// number of  adjacent swaps
static int minAdjSwaps(int [,]mat)
{
  // Stores the size of
  // the given matrix
  int N = mat.GetLength(0);
 
  // Stores the count of zero
  // at the end of each row
  int []cntZero = new int[N];
 
  // Traverse the given matrix
  for(int i = 0; i < N; i++)
  {
    // Count of 0s at the end
    // of the ith row
    for(int j = N - 1;
            j >= 0 && mat[i, j] == 0;
            j--)
    {
      cntZero[i]++;
    }
  }
 
  // Stores the count of swaps
  int cntSwaps = 0;
 
  // Traverse the cntZero array
  for(int i = 0; i < N; i++)
  {
    // If count of zero in the
    // i-th row < (N - i - 1)
    if (cntZero[i] < (N - i - 1))
    {
      // Stores the index of the row
      // where count of zero > (N-i-1)
      int First = i;
       
      while (First < N &&
             cntZero[First] < (N - i - 1))
      {
        First++;
      }
 
      // If no row found that
      // satisfy the condition
      if (First == N)
      {
        return -1;
      }
 
      // Swap the adjacent row
      while (First > i)
      {
        cntZero = swap(cntZero,
                       First, First - 1);
        First--;
        cntSwaps++;
      }
    }
  }
  return cntSwaps;
}
 
static int[] swap(int []arr,
                  int i, int j)
{
  int temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
  return arr;
}
 
// Driver Code
public static void Main(String[] args)
{
  int [,]mat = {{0, 0, 2},
                {3, 1, 0},
                {4, 0, 0}};
  Console.Write(minAdjSwaps(mat));
}
}
 
// This code is contributed by 29AjayKumar

<script>
 
// Javascript program to implement
// the above approach
 
    // Function to count the minimum
    // number of adjacent swaps
    function minAdjSwaps(mat) {
 
        // Stores the size of
        // the given matrix
        var N = mat.length;
 
        // Stores the count of zero
        // at the end of each row
        var cntZero = Array(N).fill(0);
 
        // Traverse the given matrix
        for (i = 0; i < N; i++) {
 
            // Count of 0s at the end
            // of the ith row
            for (j = N - 1; j >= 0 &&
            mat[i][j] == 0; j--)
            {
                cntZero[i]++;
            }
        }
 
        // Stores the count of swaps
        var cntSwaps = 0;
 
        // Traverse the cntZero array
        for (i = 0; i < N; i++) {
 
            // If count of zero in the
            // i-th row < (N - i - 1)
            if (cntZero[i] < (N - i - 1)) {
 
                // Stores the index of the row
                // where count of zero > (N-i-1)
                var First = i;
                while (First < N && cntZero[First] <
                (N - i - 1))
                {
                    First++;
                }
 
                // If no row found that
                // satisfy the condition
                if (First == N) {
                    return -1;
                }
 
                // Swap the adjacent row
                while (First > i) {
                    cntZero = swap(cntZero, First,
                    First - 1);
                    First--;
                    cntSwaps++;
                }
            }
        }
        return cntSwaps;
    }
 
    function swap(arr , i , j) {
        var temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
        return arr;
    }
 
    // Driver Code
     
        var mat = [ [ 0, 0, 2 ],
        [ 3, 1, 0 ],
        [ 4, 0, 0 ] ];
 
        document.write(minAdjSwaps(mat));
 
// This code contributed by gauravrajput1
 
</script>

3

Tiempo Complejidad: O(N ² )
Espacio Auxiliar: O(N)