Subsecuencia común más larga de dos arrays, de las cuales una array consta solo de elementos distintos

Dadas dos arrays firstArr[] , que consisten solo en elementos distintos, y secondArr[] , la tarea es encontrar la longitud de LCS entre estas 2 arrays.

Ejemplos:

Entrada: firstArr[] = {3, 5, 1, 8}, secondArr[] = {3, 3, 5, 3, 8}
Salida: 3.
Explicación: LCS entre estas dos arrays es {3, 5, 8} .

Entrada : primeraArr[] = {1, 2, 1}, segundaArr[] = {3}
Salida: 0

Enfoque ingenuo: siga los pasos a continuación para resolver el problema utilizando el enfoque más simple posible:

  • Inicialice una array dp[][] tal que dp[i][j] almacene la subsecuencia común más larga de firstArr[ :i] y secondArr[ :j] .
  • Recorra la array firstArr[] y para cada elemento de array de la array firstArr[] , recorra la array secondArr[] .
  • Si firstArr[i] = secondArr[j]: Establecer dp[i][j] = dp[i – 1][j – 1] + 1 .
  • De lo contrario: Establezca dp[i][j] = max(dp[ i – 1][j], dp[i][j – 1]) .

Complejidad temporal: O(N * M), donde N y M son los tamaños de las arrays firstArr[] y secondArr[] respectivamente. 
Espacio Auxiliar: O(N * M)

Enfoque eficiente: para optimizar el enfoque anterior, siga los pasos a continuación: 

  • Inicialice un Map , digamos mp , para almacenar las asignaciones map[firstArr[i]] = i , es decir, asigne elementos de la primera array a sus respectivos índices.
  • Dado que los elementos que están presentes en secondArr[] pero no en firstArr[] no son útiles en absoluto, ya que nunca pueden ser parte de una subsecuencia común, recorra la array secondArr[] y para cada elemento de la array, verifique si es presentes en el Mapa o no .
  • Si se determina que es cierto, inserte map[ secondArr [i]] en una array temporal. De lo contrario, ignóralo.
  • Encuentre la subsecuencia creciente más larga (LIS) de la array temporal obtenida e imprima su longitud como la respuesta requerida.

Ilustración: 

firstArr[] = {3, 5, 1, 8} 
secondArr={3, 3, 4, 5, 3, 8} 
Asignación : 3->0, 5->1, 1->2, 8->3 ( De firstArr) 
tempArr[] = {0, 0, 1, 0, 3} 
Por lo tanto, la longitud de LIS de tempArr[] = 3 ({0, 1, 3}) 

A continuación se muestra la implementación del enfoque anterior: 

C++

// C++ program to to implement
// the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the Longest Common
// Subsequence between the two arrays
int LCS(vector<int>& firstArr,
        vector<int>& secondArr)
{
 
    // Maps elements of firstArr[]
    // to their respective indices
    unordered_map<int, int> mp;
 
    // Traverse the array firstArr[]
    for (int i = 0; i < firstArr.size(); i++) {
        mp[firstArr[i]] = i + 1;
    }
 
    // Stores the indices of common elements
    // between firstArr[] and secondArr[]
    vector<int> tempArr;
 
    // Traverse the array secondArr[]
    for (int i = 0; i < secondArr.size(); i++) {
 
        // If current element exists in the Map
        if (mp.find(secondArr[i]) != mp.end()) {
 
            tempArr.push_back(mp[secondArr[i]]);
        }
    }
 
    // Stores lIS from tempArr[]
    vector<int> tail;
 
    tail.push_back(tempArr[0]);
 
    for (int i = 1; i < tempArr.size(); i++) {
 
        if (tempArr[i] > tail.back())
            tail.push_back(tempArr[i]);
 
        else if (tempArr[i] < tail[0])
            tail[0] = tempArr[i];
 
        else {
            auto it = lower_bound(tail.begin(),
                                  tail.end(),
                                  tempArr[i]);
            *it = tempArr[i];
        }
    }
    return (int)tail.size();
}
 
// Driver Code
int main()
{
    vector<int> firstArr = { 3, 5, 1, 8 };
    vector<int> secondArr = { 3, 3, 5, 3, 8 };
    cout << LCS(firstArr, secondArr);
    return 0;
}

Java

// Java program to to implement
// the above approach
import java.util.*;
class GFG
{
 
// Function to find the Longest Common
// Subsequence between the two arrays
static int LCS(int[] firstArr,int[] secondArr)
{
 
    // Maps elements of firstArr[]
    // to their respective indices
    HashMap<Integer,Integer> mp = new HashMap<Integer,Integer>();
 
    // Traverse the array firstArr[]
    for (int i = 0; i < firstArr.length; i++)
    {
        mp.put(firstArr[i], i + 1); 
    }
 
    // Stores the indices of common elements
    // between firstArr[] and secondArr[]
    Vector<Integer> tempArr = new Vector<>();
 
    // Traverse the array secondArr[]
    for (int i = 0; i < secondArr.length; i++)
    {
 
        // If current element exists in the Map
        if (mp.containsKey(secondArr[i]))
        {
            tempArr.add(mp.get(secondArr[i]));
        }
    }
 
    // Stores lIS from tempArr[]
    Vector<Integer> tail = new Vector<>();
    tail.add(tempArr.get(0));
 
    for (int i = 1; i < tempArr.size(); i++)
    {
        if (tempArr.get(i) > tail.lastElement())
            tail.add(tempArr.get(i));
        else if (tempArr.get(i) < tail.get(0))
            tail.add(0, tempArr.get(i));     
    }
    return (int)tail.size();
}
 
// Driver Code
public static void main(String[] args)
{
    int[] firstArr = { 3, 5, 1, 8 };
    int[] secondArr = { 3, 3, 5, 3, 8 };
    System.out.print(LCS(firstArr, secondArr));
}
}
 
// This code is contributed by gauravrajput1

Python3

# Python3 program to to implement
# the above approach
from bisect import bisect_left
 
# Function to find the Longest Common
# Subsequence between the two arrays
def LCS(firstArr, secondArr):
 
    # Maps elements of firstArr[]
    # to their respective indices
    mp = {}
 
    # Traverse the array firstArr[]
    for i in range(len(firstArr)):
        mp[firstArr[i]] = i + 1
 
    # Stores the indices of common elements
    # between firstArr[] and secondArr[]
    tempArr = []
 
    # Traverse the array secondArr[]
    for i in range(len(secondArr)):
 
        # If current element exists in the Map
        if (secondArr[i] in  mp):
            tempArr.append(mp[secondArr[i]])
 
    # Stores lIS from tempArr[]
    tail = []
    tail.append(tempArr[0])
    for i in range(1, len(tempArr)):
        if (tempArr[i] > tail[-1]):
            tail.append(tempArr[i])
        elif (tempArr[i] < tail[0]):
            tail[0] = tempArr[i]
        else :
            it = bisect_left(tail, tempArr[i])
            it = tempArr[i]
    return len(tail)
 
# Driver Code
if __name__ == '__main__':
    firstArr = [3, 5, 1, 8 ]
    secondArr = [3, 3, 5, 3, 8 ]
    print (LCS(firstArr, secondArr))
 
# This code is contributed by mohit kumar 29

C#

// C# program to to implement
// the above approach
using System;
using System.Collections.Generic;
public class GFG
{
 
// Function to find the longest Common
// Subsequence between the two arrays
static int LCS(int[] firstArr,int[] secondArr)
{
 
    // Maps elements of firstArr[]
    // to their respective indices
    Dictionary<int,int> mp = new Dictionary<int,int>();
 
    // Traverse the array firstArr[]
    for (int i = 0; i < firstArr.Length; i++)
    {
        mp.Add(firstArr[i], i + 1); 
    }
 
    // Stores the indices of common elements
    // between firstArr[] and secondArr[]
    List<int> tempArr = new List<int>();
 
    // Traverse the array secondArr[]
    for (int i = 0; i < secondArr.Length; i++)
    {
 
        // If current element exists in the Map
        if (mp.ContainsKey(secondArr[i]))
        {
            tempArr.Add(mp[secondArr[i]]);
        }
    }
 
    // Stores lIS from tempArr[]
    List<int> tail = new List<int>();
    tail.Add(tempArr[0]);
 
    for (int i = 1; i < tempArr.Count; i++)
    {
        if (tempArr[i] > tail[tail.Count-1])
            tail.Add(tempArr[i]);
        else if (tempArr[i] < tail[0])
            tail.Insert(0, tempArr[i]);     
    }
    return (int)tail.Count;
}
 
// Driver Code
public static void Main(String[] args)
{
    int[] firstArr = { 3, 5, 1, 8 };
    int[] secondArr = { 3, 3, 5, 3, 8 };
    Console.Write(LCS(firstArr, secondArr));
}
}
 
// This code is contributed by Rajput-Ji.

Javascript

<script>
 
// Javascript program to to implement
// the above approach
 
// Function to find the longest Common
// Subsequence between the two arrays
function LCS(firstArr, secondArr)
{
     
    // Maps elements of firstArr[]
    // to their respective indices
    let mp = new Map()
 
    // Traverse the array firstArr[]
    for(let i = 0; i < firstArr.length; i++)
    {
        mp.set(firstArr[i], i + 1);
    }
 
    // Stores the indices of common elements
    // between firstArr[] and secondArr[]
    let tempArr = [];
 
    // Traverse the array secondArr[]
    for(let i = 0; i < secondArr.length; i++)
    {
         
        // If current element exists in the Map
        if (mp.has(secondArr[i]))
        {
            tempArr.push(mp.get(secondArr[i]));
        }
    }
 
    // Stores lIS from tempArr[]
    let tail = [];
    tail.push(tempArr[0]);
 
    for(let i = 1; i < tempArr.length; i++)
    {
        if (tempArr[i] > tail[tail.length - 1])
            tail.push(tempArr[i]);
             
        else if (tempArr[i] < tail[0])
            tail.unshift(0, tempArr[i]);   
    }
    return tail.length;
}
 
// Driver Code
let firstArr = [ 3, 5, 1, 8 ];
let secondArr = [ 3, 3, 5, 3, 8 ];
 
document.write(LCS(firstArr, secondArr));
 
// This code is contributed by gfgking
 
</script>
Producción: 

3

 

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

Publicación traducida automáticamente

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