Saltar al contenido

Minimice los movimientos para separar pares e impares intercambiando elementos adyacentes

Dada una matriz Arr[] de tamaño NORTE, la tarea es encontrar los movimientos mínimos para separar números pares e impares intercambiando dos elementos adyacentes a la vez.

Ejemplo:

Aporte: N = 7, arreglo = {3, 5, 2, 7, 9, 11, 12}
Salida: 3
Explicación: cambiar arr[2] y viene[3] para obtener arr = {3, 5, 7, 2, 9, 11, 12}.
Movimiento 2: Intercambiar arr[3] y viene[4] para obtener arr = {3, 5, 7, 9, 2, 11, 12}.
Movimiento 3: Intercambiar arr[4] y viene[5] para obtener arr = {3, 5, 7, 9, 11, 2, 12}.
Todas las posibilidades están al principio de arr[0 . . . 4]
y pares al final de arr[5 . . . 6].

Aporte: N = 5, arreglo = {3, 5, 7, 2, 4}
Salida: 0

Acercarse:

Este problema se puede dividir en dos subproblemas:

  • Cambia todo lo extraño hacia adelante o
  • desplazar todos los impares al final (el mínimo de los cuales nos dará la respuesta óptima).

Por lo tanto, este problema se puede resolver utilizando el enfoque codicioso, contando inicialmente el número de movimientos para mover impar al principio, luego el número de movimientos para mover impar hasta el final y el mínimo de ambos si se devuelve una respuesta.

Para cambiar cualquier número cambiando en secuencia, se requieren movimientos: abdominales (j – i) Dónde y es el índice del último número de la paridad opuesta y i es el índice de la canción actual.

Siga los pasos dados para resolver el problema:

  • Cruza la matriz Arr de 0 Hasta que n-1 (decir i).
    • si Arr[i] es extraño, por favor agregue yo en InicioMudanzas y subir y.
    • reinicializar y Hasta que n-1.
  • Cruza la matriz Arr de n-1 Hasta que 0 (decir i).
    • si Arr[i] es extraño, por favor agregue tú Hasta que movimientos finales y disminuir y.
  • Retorno mínimo InicioMudanzas y movimientos finales como ultima respuesta.

A continuación se muestra la implementación de este enfoque:

C++14

 

#include <bits/stdc++.h>

using namespace std;

 

int minMovesToSegregate(int* arr, int& n)

{

    int startMoves = 0, endMoves = 0, j = 0;

    for (int i = 0; i < n; i++) {

        if (arr[i] & 1)

            startMoves += i - (j++);

    }

    j = n - 1;

    for (int i = n - 1; i >= 0; i--) {

        if (arr[i] & 1)

            endMoves += (j--) - i;

    }

    return min(startMoves, endMoves);

}

 

int main()

{

    int arr[] = { 3, 5, 2, 7, 9, 11, 12 };

    int N = sizeof(arr) / sizeof(arr[0]);

 

    

    cout << minMovesToSegregate(arr, N);

    return 0;

}

Complejidad del tiempo: A)
cuarto auxiliar: O(1)