Saltar al contenido

Verifique si la matriz se puede dividir en dos sub-matrices concatenando quién ordena la matriz

Dada una matriz de enteros A[] de tamaño norteel trabajo es verificar si la matriz se puede dividir en dos subarreglos, por lo que agregar uno de los dos al final del otro hace que la matriz se ordene.

A subserie es una matriz que se puede obtener de la matriz eliminando algunos o ningún elemento de ella. Puede o no ser una parte continua de una matriz.

Ejemplos:

Aporte: Arr[] = {1, 4, 5, 2, 3, 4}
Salida: Sí
Explicación :
Primera subserie (P): {1, 2, 3, 4};
Segunda subserie (Q): {4, 5};
La combinación de ambas subcadenas da una matriz ordenada:
P+Q = {1, 2, 3, 4} + {4, 5} = {1, 2, 3, 4, 4, 5}

Aporte: Arr[] = {1, 4, 6, 3, 5}
Salida: no

Acercarse: La idea detrás de la solución del problema es:

Haga una copia de la matriz y tipo la copia. Encuentre dos subcadenas ascendentes de la matriz que coincidan con el orden de la copia ordenada. Si los elementos combinados de ambos subarreglos forman el duplicado del arreglo ordenado, entonces tales subarreglos son posibles.

Siga los pasos a continuación para implementar la idea:

  • hacer una temperatura[] matriz que almacena todos los elementos de la matriz de entrada.
  • ordenar el temperatura[] serie.
  • Repita dos veces en la matriz de entrada sin ordenar e intente encontrar dos subarreglos ordenados, con el mismo orden que en temp[] serie.
    • Combinar estos dos subconjuntos.
    • Si la matriz fusionada es un duplicado de la temperatura[] matriz, entonces se cumple el requisito.
  • Si tales subcadenas no son posibles, devuelva «No» como respuesta.

Siga la imagen de abajo para una mejor comprensión.

Ilustración:

Considere la matriz Arr[] = {1, 4, 5, 2, 3, 4};
Asi que, temperatura[] matriz (matriz de entrada ordenada): {1, 2, 3, 4, 4, 5};

Primera iteración (encontrar la primera subserie ordenada):
=> Obtenemos los elementos 1, 2, 3 y 4 que mantienen el orden como en temp[],
=> Guárdelos en otra matriz: {1, 2, 3, 4}.

Segunda iteración (busque la segunda subcadena ordenada):
=> Obtenemos 4, 5.
=> Ahora agregue estos elementos a la nueva matriz también: {1, 2, 3, 4, 4, 5}.

Se han completado 2 iteraciones.
temperatura[] = nueva matriz

Entonces la salida será «Sí».

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

Java

 

import java.util.*;

 

class GFG {

   

    

    public static void solve(int[] arr1)

    {

        

        

        

        int[] temp = new int[arr1.length];

 

        for (int i = 0; i < arr1.length; i++) {

            temp[i] = arr1[i];

        }

        Arrays.sort(temp);

 

        

        

        int counter = 0;

 

        

        

        int[] arr = new int[arr1.length];

 

        

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

 

            

            

            for (int j = 0; j < arr1.length; j++) {

 

                

                

                if (arr1[j] == temp[counter]) {

 

                    

                    arr[counter] = arr1[j];

 

                    counter++;

                    if (counter == temp.length) {

                        break;

                    }

                }

            }

        }

        System.out.println(Arrays.equals(arr, temp) == true

                               ? "Yes"

                               : "No");

    }

 

    

    public static void main(String[] args)

    {

        int[] arr = { 1, 4, 5, 2, 3, 4 };

       

        

        solve(arr);

    }

}

Complejidad del tiempo: O(N * registro(N))
cuarto auxiliar: A)