Dada una array de N elementos. La tarea es dividir los elementos en dos arrays, digamos a1[] y a2[], de modo que una contenga elementos estrictamente crecientes y la otra contenga elementos estrictamente decrecientes y a1.size() + a2.size() = a.size() . Si no es posible hacerlo, imprima -1 o imprima ambas arrays.
Nota : puede haber varias respuestas y el orden de los elementos no debe ser el mismo en las arrays secundarias.
Ejemplos:
Entrada: a[] = {7, 2, 7, 3, 3, 1, 4}
Salida: a1[] = {1, 2, 3, 4, 7} , a2[] = {7, 3}Entrada: a[] = {1, 2, 2, 1, 1}
Salida: -1
No es posible
Enfoque : Se siguen los siguientes pasos para resolver el problema anterior:
- Inicialice dos vectores v1 y v2 que almacenan números crecientes y decrecientes.
- Utilice hashing para conocer la ocurrencia del número en la array.
- Si el número parece venir por primera vez, guárdelo en v1.
- Si el número parece venir por segunda vez, guárdelo en v2.
- Si el número aparece más de 2 veces, entonces no es posible almacenar para crear una array estrictamente creciente y estrictamente decreciente.
- Por último, ordene el primer vector en orden creciente y el segundo vector en orden decreciente e imprímalos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to print both the arrays
void PrintBothArrays(int a[], int n)
{
// Store both arrays
vector<int> v1, v2;
// Used for hashing
unordered_map<int, int> mpp;
// Iterate for every element
for (int i = 0; i < n; i++) {
// Increase the count
mpp[a[i]]++;
// If first occurrence
if (mpp[a[i]] == 1)
v1.push_back(a[i]);
// If second occurrence
else if (mpp[a[i]] == 2)
v2.push_back(a[i]);
// If occurs more than 2 times
else {
cout << "Not possible";
return;
}
}
// Sort in increasing order
sort(v1.begin(), v1.end());
// Print the increasing array
cout << "Strictly increasing array is:\n";
for (auto it : v1)
cout << it << " ";
// Sort in reverse order
sort(v2.begin(), v2.end(), greater<int>());
// Print the decreasing array
cout << "\nStrictly decreasing array is:\n";
for (auto it : v2)
cout << it << " ";
}
// Driver code
int main()
{
int a[] = { 7, 2, 7, 3, 3, 1, 4 };
int n = sizeof(a) / sizeof(a[0]);
PrintBothArrays(a, n);
return 0;
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG
{
// Function to print both the arrays
static void PrintBothArrays(int a[], int n)
{
// Store both arrays
Vector<Integer> v1 = new Vector<Integer>(),
v2 = new Vector<Integer>();
// Used for hashing
HashMap<Integer, Integer> mpp = new HashMap<>();
// Iterate for every element
for (int i = 0; i < n; i++)
{
// Increase the count
mpp.put(a[i],(mpp.get(a[i]) == null?0:mpp.get(a[i]))+1);
// If first occurrence
if (mpp.get(a[i]) == 1)
v1.add(a[i]);
// If second occurrence
else if (mpp.get(a[i]) == 2)
v2.add(a[i]);
// If occurs more than 2 times
else
{
System.out.println( "Not possible");
return;
}
}
// Sort in increasing order
Collections.sort(v1);
// Print the increasing array
System.out.println("Strictly increasing array is:");
for (int i = 0; i < v1.size(); i++)
System.out.print(v1.get(i) + " ");
// Sort
Collections.sort(v2);
Collections.reverse(v2);
// Print the decreasing array
System.out.println("\nStrictly decreasing array is:");
for (int i = 0; i < v2.size(); i++)
System.out.print(v2.get(i) + " ");
}
// Driver code
public static void main(String args[])
{
int a[] = { 7, 2, 7, 3, 3, 1, 4 };
int n = a.length;
PrintBothArrays(a, n);
}
}
// This code is contributed by Arnab Kundu
Python3
# Python3 program to implement
# the above approach
# Function to print both the arrays
def PrintBothArrays(a, n) :
# Store both arrays
v1, v2 = [], [];
# Used for hashing
mpp = dict.fromkeys(a, 0);
# Iterate for every element
for i in range(n) :
# Increase the count
mpp[a[i]] += 1;
# If first occurrence
if (mpp[a[i]] == 1) :
v1.append(a[i]);
# If second occurrence
elif (mpp[a[i]] == 2) :
v2.append(a[i]);
# If occurs more than 2 times
else :
print("Not possible");
return;
# Sort in increasing order
v1.sort();
# Print the increasing array
print("Strictly increasing array is:");
for it in v1:
print(it, end = " ");
# Sort in reverse order
v2.sort(reverse = True);
# Print the decreasing array
print("\nStrictly decreasing array is:");
for it in v2 :
print(it, end = " ")
# Driver code
if __name__ == "__main__" :
a = [ 7, 2, 7, 3, 3, 1, 4 ];
n = len(a);
PrintBothArrays(a, n);
# This code is contributed by Ryuga
C#
// C# program to implement
// the above approach
using System;
using System.Collections;
using System.Collections.Generic;
class GFG
{
// Function to print both the arrays
static void PrintBothArrays(int [] a, int n)
{
// Store both arrays
List<int> v1 = new List<int>();
List<int> v2 = new List<int>();
// Used for hashing
Dictionary<int, int> mpp = new Dictionary<int, int>();
// Iterate for every element
for (int i = 0; i < n; i++)
{
// Increase the Count
if(mpp.ContainsKey(a[i]))
mpp[a[i]] = mpp[a[i]] + 1;
else
mpp[a[i]] = 1;
// If first occurrence
if (mpp[a[i]] == 1)
v1.Add(a[i]);
// If second occurrence
else if (mpp[a[i]] == 2)
v2.Add(a[i]);
// If occurs more than 2 times
else
{
Console.WriteLine( "Not possible");
return;
}
}
// Sort in increasing order
v1.Sort();
// Print the increasing array
Console.WriteLine("Strictly increasing array is:");
for (int i = 0; i < v1.Count; i++)
Console.Write(v1[i] + " ");
// Sort
v2.Sort();
v2.Reverse();
// Print the decreasing array
Console.WriteLine("\nStrictly decreasing array is:");
for (int i = 0; i < v2.Count; i++)
Console.Write(v2[i] + " ");
}
// Driver code
public static void Main()
{
int [] a = { 7, 2, 7, 3, 3, 1, 4 };
int n = a.Length;
PrintBothArrays(a, n);
}
}
// This code is contributed by ihritik
Javascript
<script>
// Javascript implementation of the approach
// Function to print both the arrays
function PrletBothArrays(a, n)
{
// Store both arrays
let v1 = [], v2 = [];
// Used for hashing
let mpp = new Map();
// Iterate for every element
for (let i = 0; i < n; i++)
{
// Increase the count
mpp.set(a[i],(mpp.get(a[i]) == null?0:mpp.get(a[i]))+1);
// If first occurrence
if (mpp.get(a[i]) == 1)
v1.push(a[i]);
// If second occurrence
else if (mpp.get(a[i]) == 2)
v2.push(a[i]);
// If occurs more than 2 times
else
{
document.write( "Not possible");
return;
}
}
// Sort in increasing order
v1.sort();
// Print the increasing array
document.write("Strictly increasing array is:" + "<br/>");
for (let i = 0; i < v1.length; i++)
document.write(v1[i] + " ");
// Sort
v2.sort();
v2.reverse();
// Print the decreasing array
document.write("<br/>" + "\nStrictly decreasing array is:" + "<br/>");
for (let i = 0; i < v2.length; i++)
document.write(v2[i] + " ");
}
// Driver code
let a = [ 7, 2, 7, 3, 3, 1, 4 ];
let n = a.length;
PrletBothArrays(a, n);
// This code is contributed by sanjoy_62.
</script>
Producción:
Strictly increasing array is: 1 2 3 4 7 Strictly decreasing array is: 7 3
Complejidad de tiempo: O(N*logN), ya que en el peor de los casos usaremos una función de ordenación incorporada para ordenar una array de tamaño N. Donde N es el número de elementos en la array.
Espacio auxiliar: O(N), ya que estamos usando espacio adicional para el mapa y la array v1 y v2. Donde N es la longitud de la string.