Dada una secuencia fusionada que consta de dos secuencias que se fusionaron, una de ellas era estrictamente creciente y la otra estrictamente decreciente. Se insertaron elementos de secuencia creciente entre elementos de secuencia decreciente sin cambiar el orden.
Las secuencias [1, 3, 4] y [10, 4, 2] pueden producir las siguientes secuencias resultantes: [
10, 1, 3, 4, 2, 4], [1, 3, 4, 10, 4, 2] .
La siguiente secuencia no puede ser el resultado de estas inserciones:
[1, 10, 4, 4, 3, 2] porque se cambió el orden de los elementos en la secuencia creciente.
Dada una secuencia fusionada, la tarea es encontrar dos secuencias iniciales adecuadas, una de ellas estrictamente creciente y otra estrictamente decreciente.
Nota : una secuencia vacía y la secuencia que consta de un elemento se pueden considerar crecientes o decrecientes.
Ejemplos:
Entrada: arr[] = {5, 1, 3, 6, 8, 2, 9, 0, 10}
Salida: [1, 3, 6, 8, 9, 10] [5, 2, 0]Entrada: arr[] = {1, 2, 4, 0, 2}
Salida: -1
Tales secuencias no son posibles.
Método 1: podemos modificar la secuencia creciente más larga y resolver el problema requerido. Tomará tiempo O (nlogn).
Método 2: También podemos resolver este problema solo en un solo recorrido. La idea utilizada aquí es que mantiene dos arrays ordenadas.
Para un nuevo elemento x ,
- Si se puede agregar a solo una de las arrays, agréguelo.
- Si no se puede agregar a ninguno, entonces la respuesta es -1 .
- Si se puede agregar a ambos, verifique el siguiente elemento y , si y> x, luego agregue x al creciente; de lo contrario, agregue x al decreciente.
Ahora, cuando encontramos un elemento que se puede incluir en ambas secuencias, debemos decidir en función del valor del siguiente elemento. Consideremos una situación en la que necesitamos iterar sobre el valor restante x,y,z donde (x < z < y) y ya tenemos el último elemento de la secuencia creciente y decreciente como inc y dec respectivamente de la parte visitada del formación.
Caso 1: x<y e inc<x<dec
por lo que podemos incluir x en cualquier secuencia.
Si lo incluimos en secuencia decreciente entonces dec se convertirá en x. Y luego, para y solo tenemos una opción, es decir, incluirlo en secuencia creciente cuando y>dec e inc se convierte en y. Si hacemos esto, no podemos insertar z en ninguna secuencia como z>dec y z<inc.
Pero si incluimos x en una secuencia creciente (inc se convierte en x) e y en una secuencia decreciente (dec se convierte en y) siguiendo la misma lógica, entonces podemos colocar z en cualquier secuencia y obtener una respuesta.
Caso 2: x>=y e inc<x<dec
sigue la misma lógica que el anterior.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to print strictly increasing and
// strictly decreasing sequence if possible
void Find_Sequence(int arr[], int n)
{
// Arrays to store strictly increasing and
// decreasing sequence
vector<int> inc_arr, dec_arr;
// Initializing last element of both sequence
int flag = 0;
long inc = -1, dec = 1e7;
// Iterating through the array
for (int i = 0; i < n; i++)
{
// If current element can be appended
// to both the sequences
if (inc < arr[i] && arr[i] < dec)
{
// If next element is greater than
// the current element
// Then append it to the strictly
// increasing array
if (arr[i] < arr[i + 1])
{
inc = arr[i];
inc_arr.emplace_back(arr[i]);
}
// Otherwise append it to the
// strictly decreasing array
else
{
dec = arr[i];
dec_arr.emplace_back(arr[i]);
}
}
// If current element can be appended
// to the increasing sequence only
else if (inc < arr[i])
{
inc = arr[i];
inc_arr.emplace_back(arr[i]);
}
// If current element can be appended
// to the decreasing sequence only
else if (dec > arr[i])
{
dec = arr[i];
dec_arr.emplace_back(arr[i]);
}
// Else we can not make such sequences
// from the given array
else
{
cout << -1 << endl;
flag = 1;
break;
}
}
// Print the required sequences
if (!flag)
{
for (auto i = inc_arr.begin();
i != inc_arr.end(); i++)
cout << *i << " ";
cout << endl;
for (auto i = dec_arr.begin();
i != dec_arr.end(); i++)
cout << *i << " ";
cout << endl;
}
}
// Driver code
int main()
{
int arr[] = { 5, 1, 3, 6, 8, 2, 9, 0, 10 };
int n = sizeof(arr) / sizeof(arr[0]);
Find_Sequence(arr, n);
}
// This code is contributed by sanjeev2552
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
// Function to print strictly increasing and
// strictly decreasing sequence if possible
static void Find_Sequence(int[] arr, int n)
{
// Arrays to store strictly increasing and
// decreasing sequence
Vector<Integer> inc_arr = new Vector<>(),
dec_arr = new Vector<>();
// Initializing last element of both sequence
int flag = 0;
long inc = -1, dec = (long) 1e7;
// Iterating through the array
for (int i = 0; i < n; i++)
{
// If current element can be appended
// to both the sequences
if (inc < arr[i] && arr[i] < dec)
{
// If next element is greater than
// the current element
// Then append it to the strictly
// increasing array
if (arr[i] < arr[i + 1])
{
inc = arr[i];
inc_arr.add(arr[i]);
}
// Otherwise append it to the
// strictly decreasing array
else
{
dec = arr[i];
dec_arr.add(arr[i]);
}
}
// If current element can be appended
// to the increasing sequence only
else if (inc < arr[i])
{
inc = arr[i];
inc_arr.add(arr[i]);
}
// If current element can be appended
// to the decreasing sequence only
else if (dec > arr[i])
{
dec = arr[i];
dec_arr.add(arr[i]);
}
// Else we can not make such sequences
// from the given array
else
{
System.out.println(-1);
flag = 1;
break;
}
}
// Print the required sequences
if (flag == 0)
{
for (int i : inc_arr)
System.out.print(i + " ");
System.out.println();
for (int i : dec_arr)
System.out.print(i + " ");
System.out.println();
}
}
// Driver Code
public static void main(String[] args)
{
int[] arr = { 5, 1, 3, 6, 8, 2, 9, 0, 10 };
int n = arr.length;
Find_Sequence(arr, n);
}
}
// This code is contributed by
// sanjeev2552
Python3
# Python3 implementation of the approach
# Function to print strictly increasing and
# strictly decreasing sequence if possible
def Find_Sequence(array, n):
# Arrays to store strictly increasing and
# decreasing sequence
inc_arr, dec_arr =[], []
# Initializing last element of both sequence
inc, dec = -1, 1e7
# Iterating through the array
for i in range(n):
# If current element can be appended
# to both the sequences
if inc < array[i] < dec:
# If next element is greater than
# the current element
# Then append it to the strictly
# increasing array
if array[i] < array[i + 1]:
inc = array[i]
inc_arr.append(array[i])
# Otherwise append it to the
# strictly decreasing array
else:
dec = array[i]
dec_arr.append(array[i])
# If current element can be appended
# to the increasing sequence only
elif inc < array[i]:
inc = array[i]
inc_arr.append(array[i])
# If current element can be appended
# to the decreasing sequence only
elif dec > array[i]:
dec = array[i]
dec_arr.append(array[i])
# Else we can not make such sequences
# from the given array
else:
print('-1')
break
# Print the required sequences
else:
print(inc_arr, dec_arr)
# Driver code
arr = [5, 1, 3, 6, 8, 2, 9, 0, 10]
n = len(arr)
Find_Sequence(arr, n)
C#
// C# implementation of the approach
using System;
using System.Collections;
using System.Collections.Generic;
class GFG{
// Function to print strictly increasing and
// strictly decreasing sequence if possible
static void Find_Sequence(int[] arr, int n)
{
// Arrays to store strictly increasing and
// decreasing sequence
ArrayList inc_arr = new ArrayList();
ArrayList dec_arr = new ArrayList();
// Initializing last element of both sequence
int flag = 0;
long inc = -1, dec = (long)1e7;
// Iterating through the array
for(int i = 0; i < n; i++)
{
// If current element can be appended
// to both the sequences
if (inc < arr[i] && arr[i] < dec)
{
// If next element is greater than
// the current element
// Then append it to the strictly
// increasing array
if (arr[i] < arr[i + 1])
{
inc = arr[i];
inc_arr.Add(arr[i]);
}
// Otherwise append it to the
// strictly decreasing array
else
{
dec = arr[i];
dec_arr.Add(arr[i]);
}
}
// If current element can be appended
// to the increasing sequence only
else if (inc < arr[i])
{
inc = arr[i];
inc_arr.Add(arr[i]);
}
// If current element can be appended
// to the decreasing sequence only
else if (dec > arr[i])
{
dec = arr[i];
dec_arr.Add(arr[i]);
}
// Else we can not make such sequences
// from the given array
else
{
Console.Write(-1);
flag = 1;
break;
}
}
// Print the required sequences
if (flag == 0)
{
foreach(int i in inc_arr)
Console.Write(i + " ");
Console.Write('\n');
foreach(int i in dec_arr)
Console.Write(i + " ");
Console.Write('\n');
}
}
// Driver Code
public static void Main(string[] args)
{
int[] arr = { 5, 1, 3, 6, 8,
2, 9, 0, 10 };
int n = arr.Length;
Find_Sequence(arr, n);
}
}
// This code is contributed by rutvik_56
PHP
<?php
// Php implementation of the approach
// Function to print strictly increasing and
// strictly decreasing sequence if possible
function Find_Sequence($arr, $n)
{
// Arrays to store strictly increasing and
// decreasing sequence
$inc_arr = array(); $dec_arr = array();
// Initializing last element of both sequence
$inc = -1; $dec = 1e7;
// Iterating through the array
for ($i = 0; $i < $n ; $i++)
{
// If current element can be appended
// to both the sequences
if ($inc < $arr[$i] && $arr[$i] < $dec)
{
// If next element is greater than
// the current element
// Then append it to the strictly
// increasing array
if ($arr[$i] < $arr[$i + 1])
{
$inc = $arr[$i];
array_push($inc_arr, $arr[$i]);
}
// Otherwise append it to the
// strictly decreasing array
else
{
$dec = $arr[$i];
array_push($dec_arr, $arr[$i]);
}
}
// If current element can be appended
// to the increasing sequence only
else if ($inc < $arr[$i])
{
$inc = $arr[$i];
array_push($inc_arr, $arr[$i]);
}
// If current element can be appended
// to the decreasing sequence only
else if($dec > $arr[$i])
{
$dec = $arr[$i];
array_push($dec_arr, $arr[$i]);
}
// Else we can not make such sequences
// from the given array
else
{
echo '-1';
break;
}
}
// Print the required sequences
print_r($inc_arr);
print_r($dec_arr);
}
// Driver code
$arr = array(5, 1, 3, 6, 8, 2, 9, 0, 10);
$n = count($arr);
Find_Sequence($arr, $n);
// This code is contributed by Ryuga
?>
Javascript
<script>
// Javascript implementation of the approach
// Function to print strictly increasing and
// strictly decreasing sequence if possible
function Find_Sequence(arr, n)
{
// Arrays to store strictly increasing and
// decreasing sequence
let inc_arr =[],
dec_arr = [];
// Initializing last element of both sequence
let flag = 0;
let inc = -1, dec = 1e7;
// Iterating through the array
for (let i = 0; i < n; i++)
{
// If current element can be appended
// to both the sequences
if (inc < arr[i] && arr[i] < dec)
{
// If next element is greater than
// the current element
// Then append it to the strictly
// increasing array
if (arr[i] < arr[i + 1])
{
inc = arr[i];
inc_arr.push(arr[i]);
}
// Otherwise append it to the
// strictly decreasing array
else
{
dec = arr[i];
dec_arr.push(arr[i]);
}
}
// If current element can be appended
// to the increasing sequence only
else if (inc < arr[i])
{
inc = arr[i];
inc_arr.push(arr[i]);
}
// If current element can be appended
// to the decreasing sequence only
else if (dec > arr[i])
{
dec = arr[i];
dec_arr.push(arr[i]);
}
// Else we can not make such sequences
// from the given array
else
{
document.write(-1);
flag = 1;
break;
}
}
// Print the required sequences
if (flag == 0)
{
document.write("[");
for (let i in inc_arr)
document.write( inc_arr[i] + " ");
document.write("] ");
document.write("[");
for (let i in dec_arr)
document.write( dec_arr[i] + " ");
document.write("]");
}
}
// Driver Code
let arr = [ 5, 1, 3, 6, 8, 2, 9, 0, 10 ];
let n = arr.length;
Find_Sequence(arr, n);
// This code is contributed by target_2.
</script>
[1, 3, 6, 8, 9, 10] [5, 2, 0]
Complejidad de tiempo: O (n), donde n es el tamaño de la array dada.
Complejidad espacial: O(n), se requiere espacio adicional para almacenar secuencias estrictamente crecientes y decrecientes.
Publicación traducida automáticamente
Artículo escrito por saurabh sisodia y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA