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>
Producción
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