Divida los elementos de la array en una secuencia estrictamente creciente y decreciente

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.

Publicación traducida automáticamente

Artículo escrito por Striver y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *