Dada una array arr que contiene N enteros únicos. La tarea es calcular el número mínimo de deques necesarios para ordenar la array.
Ejemplo :
Entrada : arr[] = {3, 6, 0, 9, 5, 4}
Salida : 2
Explicación :
Crear un nuevo deque d1 = {3}.
Crea un nuevo deque d2 = {6}.
Empuje 0 en el frente de d1; d1 = {0, 3}
Empuje 9 en la parte posterior de d2; d2 = {6, 9}
Empuje 5 al frente de d2; d2 = {5, 6, 9}
Empuje 4 al frente de d2; d2 = {4, 5, 6, 9}
Por lo tanto, se requieren 2 mínimos 2 deques.Entrada : arr[] = {50, 45, 55, 60, 65, 40, 70, 35, 30, 75}
Salida : 1
Enfoque : El problema anterior se puede resolver con avidez . Siga los pasos a continuación para resolver el problema:
- Cree dos arrays, frentes y reversos , que almacenarán los elementos del frente y del reverso de todos los deques.
- Iterar para todos los elementos de la array. Para cada elemento arr[i] , el elemento actual se puede insertar en una deque preexistente si:
- Existe un fronts[j] que es mayor que arr[i] porque esto significa que este arr[i] se puede colocar delante de este deque. Pero si existe otro elemento entre arr[i] y fronts[j] en la array arr , entonces no se puede empujar porque empujar alterará el orden de los elementos en deques de tal manera que estos deques no se pueden organizar en forma ordenada array, incluso estando ordenados individualmente.
- Del mismo modo, verifique los respaldos de la array utilizando el paso mencionado anteriormente.
- Si un elemento no se puede insertar en una de las deque, se debe crear otra deque para ese elemento. Por lo tanto, empuje el elemento tanto en la parte delantera como en la trasera porque es tanto la parte delantera como la trasera del deque recién creado.
- Ahora, devuelva el tamaño de los frentes (o reversos) de la array como respuesta a esta pregunta.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; int minDeques(vector<int> arr) { // Vectors to store the front and back // element of all present deques vector<int> fronts, backs; // Iterate through all array elements for (int i = 0; i < arr.size(); i++) { // Bool variable to check if the array // element has already been pushed or not bool hasBeenPushed = false; for (int j = 0; j < fronts.size(); j++) { // Check for all deques where arr[i] // can be pushed in the front if (arr[i] < fronts[j]) { bool isSafe = true; for (int k = 0; k < arr.size(); k++) { if (arr[i] < arr[k] && arr[k] < fronts[j]) { isSafe = false; break; } } // Push in front of an already // existing deque if (isSafe) { fronts[j] = arr[i]; hasBeenPushed = true; break; } } // Check for all deques where arr[i] // can be pushed in the back if (arr[i] > backs[j]) { bool isSafe = true; for (int k = 0; k < arr.size(); k++) { if (arr[i] > arr[k] && arr[k] > backs[j]) { isSafe = false; break; } } // Push in back of an already // existing deque if (isSafe) { backs[j] = arr[i]; hasBeenPushed = true; break; } } } // If arr[i] cannot be pushed to any // of the existing deques, then push // it in a new deque if (!hasBeenPushed) { fronts.push_back(arr[i]); backs.push_back(arr[i]); } } return fronts.size(); } // Driver Code int main() { vector<int> arr = { 3, 6, 0, 9, 5, 4 }; cout << minDeques(arr); }
Java
// Java program for the above approach import java.util.*; class GFG{ public static int minDeques(int[] arr) { // Vectors to store the front and back // element of all present deques ArrayList<Integer> fronts = new ArrayList<Integer>(); ArrayList<Integer> backs = new ArrayList<Integer>(); // Iterate through all array elements for (int i = 0; i < arr.length; i++) { // Bool variable to check if the array // element has already been pushed or not boolean hasBeenPushed = false; for (int j = 0; j < fronts.size(); j++) { // Check for all deques where arr[i] // can be pushed in the front if (arr[i] < fronts.get(j)) { boolean isSafe = true; for (int k = 0; k < arr.length; k++) { if (arr[i] < arr[k] && arr[k] < fronts.get(j)) { isSafe = false; break; } } // Push in front of an already // existing deque if (isSafe) { fronts.set(j, arr[i]); hasBeenPushed = true; break; } } // Check for all deques where arr[i] // can be pushed in the back if (arr[i] > backs.get(j)) { Boolean isSafe = true; for (int k = 0; k < arr.length; k++) { if (arr[i] > arr[k] && arr[k] > backs.get(j)) { isSafe = false; break; } } // Push in back of an already // existing deque if (isSafe) { backs.set(j, arr[i]); hasBeenPushed = true; break; } } } // If arr[i] cannot be pushed to any // of the existing deques, then push // it in a new deque if (!hasBeenPushed) { fronts.add(arr[i]); backs.add(arr[i]); } } return fronts.size(); } // Driver Code public static void main(String args[]) { int[] arr = { 3, 6, 0, 9, 5, 4 }; System.out.println(minDeques(arr)); } } // This code is contributed by saurabh_jaiswal..
Python3
# python program for the above approach def minDeques(arr): # Vectors to store the front and back # element of all present deques fronts = [] backs = [] # Iterate through all array elements for i in range(0, len(arr)): # Bool variable to check if the array # element has already been pushed or not hasBeenPushed = False for j in range(0, len(fronts)): # Check for all deques where arr[i] # can be pushed in the front if (arr[i] < fronts[j]): isSafe = True for k in range(0, len(arr)): if (arr[i] < arr[k] and arr[k] < fronts[j]): isSafe = False break # Push in front of an already # existing deque if (isSafe): fronts[j] = arr[i] hasBeenPushed = True break # Check for all deques where arr[i] # can be pushed in the back if (arr[i] > backs[j]): isSafe = True for k in range(0, len(arr)): if (arr[i] > arr[k] and arr[k] > backs[j]): isSafe = False break # Push in back of an already # existing deque if (isSafe): backs[j] = arr[i] hasBeenPushed = True break # If arr[i] cannot be pushed to any # of the existing deques, then push # it in a new deque if (not hasBeenPushed): fronts.append(arr[i]) backs.append(arr[i]) return len(fronts) # Driver Code if __name__ == "__main__": arr = [3, 6, 0, 9, 5, 4] print(minDeques(arr)) # This code is contributed by rakeshsahni
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG { static int minDeques(List<int> arr) { // Vectors to store the front and back // element of all present deques List<int> fronts = new List<int>(); List<int> backs = new List<int>(); // Iterate through all array elements for (int i = 0; i < arr.Count; i++) { // Bool variable to check if the array // element has already been pushed or not bool hasBeenPushed = false; for (int j = 0; j < fronts.Count; j++) { // Check for all deques where arr[i] // can be pushed in the front if (arr[i] < fronts[j]) { bool isSafe = true; for (int k = 0; k < arr.Count; k++) { if (arr[i] < arr[k] && arr[k] < fronts[j]) { isSafe = false; break; } } // Push in front of an already // existing deque if (isSafe) { fronts[j] = arr[i]; hasBeenPushed = true; break; } } // Check for all deques where arr[i] // can be pushed in the back if (arr[i] > backs[j]) { bool isSafe = true; for (int k = 0; k < arr.Count; k++) { if (arr[i] > arr[k] && arr[k] > backs[j]) { isSafe = false; break; } } // Push in back of an already // existing deque if (isSafe) { backs[j] = arr[i]; hasBeenPushed = true; break; } } } // If arr[i] cannot be pushed to any // of the existing deques, then push // it in a new deque if (!hasBeenPushed) { fronts.Add(arr[i]); backs.Add(arr[i]); } } return fronts.Count; } // Driver Code public static void Main() { List<int> arr = new List<int>{ 3, 6, 0, 9, 5, 4 }; Console.WriteLine(minDeques(arr)); } } // This code is contributed by ukasp.
Javascript
<script> // Javascript program for the above approach function minDeques(arr) { // Vectors to store the front and back // element of all present deques let fronts = [], backs = []; // Iterate through all array elements for (let i = 0; i < arr.length; i++) { // let variable to check if the array // element has already been pushed or not let hasBeenPushed = false; for (let j = 0; j < fronts.length; j++) { // Check for all deques where arr[i] // can be pushed in the front if (arr[i] < fronts[j]) { let isSafe = true; for (let k = 0; k < arr.length; k++) { if (arr[i] < arr[k] && arr[k] < fronts[j]) { isSafe = false; break; } } // Push in front of an already // existing deque if (isSafe) { fronts[j] = arr[i]; hasBeenPushed = true; break; } } // Check for all deques where arr[i] // can be pushed in the back if (arr[i] > backs[j]) { let isSafe = true; for (let k = 0; k < arr.length; k++) { if (arr[i] > arr[k] && arr[k] > backs[j]) { isSafe = false; break; } } // Push in back of an already // existing deque if (isSafe) { backs[j] = arr[i]; hasBeenPushed = true; break; } } } // If arr[i] cannot be pushed to any // of the existing deques, then push // it in a new deque if (!hasBeenPushed) { fronts.push(arr[i]); backs.push(arr[i]); } } return fronts.length; } // Driver Code let arr = [3, 6, 0, 9, 5, 4]; document.write(minDeques(arr)); // This code is contributed by saurabh_jaiswal. </script>
2
Complejidad de tiempo: O(N^3)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por kartikmodi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA