Encuentre la secuencia original de Array que contiene la secuencia fusionada muchas veces en orden

Posted on by Rudeus Greyrat

Dado un número N y una array arr[] que consisten en fusionar una secuencia de longitud N de enteros distintos cualquier número de veces manteniendo el orden relativo de los elementos en la secuencia inicial. La tarea es encontrar la secuencia inicial de longitud N manteniendo el orden correcto.
 

Ejemplos:

Entrada: N = 4, arr[] = {1, 13, 1, 24, 13, 24, 2, 2}
Salida: 1 13 24 2 
Explicación: 
Aquí la secuencia dada se obtiene fusionando 1 13 24 2 manteniendo el relativo orden de elementos. Por lo tanto, la respuesta es 1 13 24 2.

Entrada: N = 3, arr[] = {3, 2, 3, 1, 2, 3, 2, 1, 1}
Salida: 3 2 1
Explicación:
Aquí la secuencia dada se obtiene fusionando 3 2 1 manteniendo el relativo orden de elementos. Por lo tanto, la respuesta es 3 2 1.

Enfoque: La idea es observar que el elemento que aparece primero en la secuencia dada es el primer elemento de la secuencia restaurada resultante. Tome ese elemento en nuestra secuencia restaurada y no incluya duplicados de la secuencia dada. Realiza lo mismo con el resto de elementos hasta llegar al final. La idea puede ser implementada tanto por Map como por Set en C++.

Usando el mapa

  1. Atraviesa la secuencia dada de izquierda a derecha.
  2. El elemento que entra por primera vez en la secuencia se tiene en cuenta y se marca mediante un mapa.
  3. Los elementos marcados durante el desplazamiento se ignoran.
  4. El Paso 2 y el Paso 3 continúan hasta que se alcanza el final de la secuencia dada.

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;
 
// Function that returns the restored
// permutation
vector<int> restore(int arr[], int N)
{
    // Vector to store the result
    vector<int> result;
 
    // Map to mark the elements
    // which are taken in result
    map<int, int> mp;
    for (int i = 0; i < N; i++) {
 
        // Check if the element is
        // coming first time
        if (mp[arr[i]] == 0) {
 
            // Push in result vector
            result.push_back(arr[i]);
 
            // Mark it in the map
            mp[arr[i]]++;
        }
    }
 
    // Return the answer
    return result;
}
 
// Function to print the result
void print_result(vector<int> result)
{
    for (int i = 0; i < result.size(); i++)
        cout << result[i] << " ";
}
 
// Driver Code
int main()
{
    // Given Array
    int arr[] = { 1, 13, 1, 24, 13, 24, 2, 2 };
 
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function Call
    print_result(restore(arr, N));
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
class GFG{
 
// Function that returns the restored
// permutation
static Vector<Integer> restore(int arr[], int N)
{
    // Vector to store the result
    Vector<Integer> result = new Vector<>();
 
    // Map to mark the elements
    // which are taken in result
    HashMap<Integer,
            Integer> mp = new HashMap<Integer,
                                      Integer>();
    for (int i = 0; i < N; i++)
    {
 
        // Check if the element is
        // coming first time
        if (mp.containsKey(arr[i]) &&
            mp.get(arr[i]) == 0)
        {
 
            // Push in result vector
            result.add(arr[i]);
 
            // Mark it in the map
            if(mp.containsKey(arr[i]))
            {
                mp.put(arr[i], mp.get(arr[i]) + 1);
            }
            else
            {
                mp.put(arr[i], 1);
            }
        }
        else
            mp.put(arr[i], 0);
    }
 
    // Return the answer
    return result;
}
 
// Function to print the result
static void print_result(Vector<Integer> result)
{
    for (int i = 0; i < result.size(); i++)
        System.out.print(result.get(i) + " ");
}
 
// Driver Code
public static void main(String[] args)
{
    // Given Array
    int arr[] = { 1, 13, 1, 24, 13, 24, 2, 2 };
 
    int N = arr.length;
 
    // Function Call
    print_result(restore(arr, N));
}
}
 
// This code is contributed by Rajput-Ji

Python3

# Python3 program for the above approach
 
# Function that returns the restored
# permutation
def restore(arr, N):
     
    # List to store the result
    result = []
     
    # Map to mark the elements
    # which are taken in result
    mp = {}
     
    for i in range(N):
         
        # Checking if the element is
        # coming first time
        if not arr[i] in mp:
             
            # Push in result vector
            result.append(arr[i])
             
            # Mark it in the map
            mp[arr[i]] = 1
             
    # Return the answer
    return result
 
# Function to print the result
def print_result(result):
     
    for i in range(len(result)):
        print(result[i], end = " ")
         
# Driver code
def main():
     
    # Given array
    arr = [ 1, 13, 1, 24, 13, 24, 2, 2 ]
    N = len(arr)
     
    # Function call
    print_result(restore(arr, N))
     
main()
     
# This code is contributed by Stuti Pathak

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function that returns the restored
// permutation
static List<int> restore(int []arr, int N)
{
     
    // List to store the result
    List<int> result = new List<int>();
 
    // Map to mark the elements
    // which are taken in result
    Dictionary<int,
               int> mp = new Dictionary<int,
                                        int>();
    for(int i = 0; i < N; i++)
    {
         
        // Check if the element is
        // coming first time
        if (mp.ContainsKey(arr[i]) &&
            mp[arr[i]] == 0)
        {
             
            // Push in result vector
            result.Add(arr[i]);
 
            // Mark it in the map
            if(mp.ContainsKey(arr[i]))
            {
                mp[arr[i]] = mp[arr[i]] + 1;
            }
            else
            {
                mp.Add(arr[i], 1);
            }
        }
        else
            mp.Add(arr[i], 0);
    }
 
    // Return the answer
    return result;
}
 
// Function to print the result
static void print_result(List<int> result)
{
    for(int i = 0; i < result.Count; i++)
        Console.Write(result[i] + " ");
}
 
// Driver Code
public static void Main(String[] args)
{
     
    // Given Array
    int []arr = { 1, 13, 1, 24, 13, 24, 2, 2 };
 
    int N = arr.Length;
 
    // Function call
    print_result(restore(arr, N));
}
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
  
// Javascript program for the above approach
 
// Function that returns the restored
// permutation
function restore(arr, N)
{
    // Vector to store the result
    var result = [];
 
    // Map to mark the elements
    // which are taken in result
    var mp = new Map();
 
    for (var i = 0; i < N; i++) {
 
        // Check if the element is
        // coming first time
        if (!mp.has(arr[i])) {
 
            // Push in result vector
            result.push(arr[i]);
 
            // Mark it in the map
            mp.set(arr[i], mp.get(arr[i])+1);
        }
    }
 
    // Return the answer
    return result;
}
 
// Function to print the result
function print_result(result)
{
    for (var i = 0; i < result.length; i++)
    {
        document.write( result[i] + " ");
    }
         
}
 
// Driver Code
// Given Array
var arr = [1, 13, 1, 24, 13, 24, 2, 2];
var N = arr.length;
// Function Call
print_result(restore(arr, N));
 
</script>
Producción: 

1 13 24 2

 

Complejidad temporal: O(N)
Espacio auxiliar: O(N)

usando conjunto

  1. Atraviesa la secuencia dada de izquierda a derecha.
  2. Se toma un contador y se inicializa como 1.
  3. Inserte los elementos en el conjunto uno por uno. Si en algún momento el tamaño del conjunto y el contador es el mismo, el elemento se tiene en cuenta y el contador se incrementa en 1.
  4. Los pasos 3 y 4 se continúan hasta que se llega al final de la secuencia dada.

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;
 
// Function that returns the restored
// permutation
vector<int> restore(int arr[], int N)
{
    // Vector to store the result
    vector<int> result;
    int count1 = 1;
 
    // Set to insert unique elements
    set<int> s;
    for (int i = 0; i < N; i++) {
 
        s.insert(arr[i]);
 
        // Check if the element is
        // coming first time
        if (s.size() == count1) {
 
            // Push in result vector
            result.push_back(arr[i]);
 
            count1++;
        }
    }
 
    return result;
}
 
// Function to print the result
void print_result(vector<int> result)
{
    for (int i = 0; i < result.size(); i++)
        cout << result[i] << " ";
}
 
// Driver Code
int main()
{
    // Given Array
    int arr[] = { 1, 13, 1, 24, 13, 24, 2, 2 };
 
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function Call
    print_result(restore(arr, N));
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// Function that returns the restored
// permutation
static Vector<Integer> restore(int arr[], int N)
{
     
    // Vector to store the result
    Vector<Integer> result = new Vector<Integer>();
     
    int count1 = 1;
 
    // Set to insert unique elements
    HashSet<Integer> s = new HashSet<Integer>();
     
    for(int i = 0; i < N; i++)
    {
        s.add(arr[i]);
 
        // Check if the element is
        // coming first time
        if (s.size() == count1)
        {
             
            // Push in result vector
            result.add(arr[i]);
            count1++;
        }
    }
    return result;
}
 
// Function to print the result
static void print_result(Vector<Integer> result)
{
    for(int i = 0; i < result.size(); i++)
        System.out.print(result.get(i) + " ");
}
 
// Driver Code
public static void main(String[] args)
{
     
    // Given Array
    int arr[] = { 1, 13, 1, 24, 13, 24, 2, 2 };
 
    int N = arr.length;
 
    // Function call
    print_result(restore(arr, N));
}
}
 
// This code is contributed by Princi Singh

Python3

# Python3 program for the
# above approach
 
# Function that returns the
# restored permutation
def restore(arr, N):
 
    # Vector to store the
    # result
    result = []
    count1 = 1
 
    # Set to insert unique
    # elements
    s = set([])
     
    for i in range(N):
        s.add(arr[i])
 
        # Check if the element is
        # coming first time
        if (len(s) == count1):
 
            # Push in result vector
            result.append(arr[i])
 
            count1 += 1
 
    return result
 
# Function to print the
# result
def print_result(result):
 
    for i in range(len(result)):
        print(result[i],
              end = " ")
 
# Driver Code
if __name__ == "__main__":
 
    # Given Array
    arr = [1, 13, 1, 24,
           13, 24, 2, 2]
 
    N = len(arr)
 
    # Function Call
    print_result(restore(arr, N))
 
# This code is contributed by Chitranayal

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
 
// Function that returns the restored
// permutation
static List<int> restore(int []arr, int N)
{
     
    // List to store the result
    List<int> result = new List<int>();
     
    int count1 = 1;
 
    // Set to insert unique elements
    HashSet<int> s = new HashSet<int>();
     
    for(int i = 0; i < N; i++)
    {
        s.Add(arr[i]);
 
        // Check if the element is
        // coming first time
        if (s.Count == count1)
        {
             
            // Push in result vector
            result.Add(arr[i]);
            count1++;
        }
    }
    return result;
}
 
// Function to print the result
static void print_result(List<int> result)
{
    for(int i = 0; i < result.Count; i++)
        Console.Write(result[i] + " ");
}
 
// Driver Code
public static void Main(String[] args)
{
     
    // Given Array
    int []arr = { 1, 13, 1, 24, 13, 24, 2, 2 };
 
    int N = arr.Length;
 
    // Function call
    print_result(restore(arr, N));
}
}
 
// This code is contributed by PrinciRaj1992

Javascript

<script>
 
// Javascript program for the above approach
 
// Function that returns the restored
// permutation
function restore(arr, N)
{
     
    // Vector to store the result
    let result = [];
      
    let count1 = 1;
  
    // Set to insert unique elements
    let s = new Set();
      
    for(let i = 0; i < N; i++)
    {
        s.add(arr[i]);
  
        // Check if the element is
        // coming first time
        if (s.size == count1)
        {
             
            // Push in result vector
            result.push(arr[i]);
            count1++;
        }
    }
    return result;
}
 
// Function to print the result
function print_result(result)
{
    for(let i = 0; i < result.length; i++)
        document.write(result[i] + " ");
}
 
// Driver Code
let arr = [ 1, 13, 1, 24, 13, 24, 2, 2 ];
let N = arr.length;
 
// Function call
print_result(restore(arr, N));
 
// This code is contributed by avanitrachhadiya2155
 
</script>
Producción: 

1 13 24 2

 

Complejidad temporal: O(N)
Espacio auxiliar: O(N)

Publicación traducida automáticamente

Artículo escrito por claudia 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 *