Minimice los elementos que se agregarán a una array dada de modo que contenga otra array dada como su subsecuencia

Dada una array A[] que consta de N enteros distintos y otra array B[] que consta de M enteros, la tarea es encontrar el número mínimo de elementos que se agregarán a la array B[] de modo que la array A[] se convierta en el subsecuencia de la array B[] .

Ejemplos:

Entrada: N = 5, M = 6, A[] = {1, 2, 3, 4, 5}, B[] = {2, 5, 6, 4, 9, 12}
Salida: 3
Explicación:
A continuación se muestran los elementos que deben agregarse:
1) Agregar 1 antes del elemento 2 de B[]
2) Agregar 3 después del elemento 6 de B[]
3) Agregar 5 en la última posición de B[].
Por lo tanto, la array resultante B[] es {1, 2, 5, 6, 3, 4, 9, 12, 5}.
Por tanto, A[] es la subsecuencia de B[] después de sumar 3 elementos.

Entrada: N = 5, M = 5, A[] = {3, 4, 5, 2, 7}, B[] = {3, 4, 7, 9, 2}
Salida: 2
Explicación:
A continuación se muestran los elementos que deben agregarse:
1) Agregue 5 después del elemento 4.
2) Agregue 2 después del elemento 5.
Por lo tanto, la array resultante B[] es {3, 4, 5, 2, 7, 9, 2}.
Por lo tanto, se requieren 2 elementos para ser agregados.

Enfoque ingenuo: consulte la publicación anterior de este artículo para conocer el enfoque más simple para resolver el problema.

Complejidad de Tiempo: O(N * 2 ^M )
Espacio Auxiliar: O(M + N)

Enfoque de programación dinámica : consulte la publicación anterior de este artículo para conocer elenfoque basado en la subsecuencia común más larga .

Complejidad de Tiempo: O(N * M)
Espacio Auxiliar: O(N * M)

Enfoque eficiente: la idea es similar a encontrar la subsecuencia creciente más larga ( LIS ) de la array B[] . Siga los pasos a continuación para resolver el problema:

Considere los elementos de la array B[] que están presentes en la array A[] y almacene los índices de cada elemento de la array A[] en un mapa
Luego, busque la array LIS subseq[] mediante la búsqueda binaria , que consiste en los índices en orden creciente.
Finalmente, la cantidad mínima de elementos que se insertarán en la array B[] es igual a N – len(LIS) , donde len(LIS) se calcula mediante la búsqueda binaria en los pasos anteriores.

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 to return minimum
// element to be added in array
// B so that array A become
// subsequence of array B
int minElements(int A[], int B[],
                int N, int M)
{
  // Stores indices of the
  // array elements
  map<int, int> map;
 
  // Iterate over the array
  for (int i = 0; i < N; i++)
  {
    // Store the indices of
    // the array elements
    map[A[i]] = i;
  }
 
  // Stores the LIS
  vector<int> subseq;
 
  int l = 0, r = -1;
 
  for (int i = 0; i < M; i++)
  {
    // Check if element B[i]
    // is in array A[]
    if (map.find(B[i]) !=
        map.end())
    {
      int e = map[B[i]];
 
      // Perform Binary Search
      while (l <= r)
      {
        // Find the value of
        // mid m
        int m = l + (r - l) / 2;
 
        // Update l and r
        if (subseq[m] < e)
          l = m + 1;
        else
          r = m - 1;
      }
 
      // If found better element
      // 'e' for pos r + 1
      if (r + 1 < subseq.size())
      {
        subseq[r + 1] = e;
      }
 
      // Otherwise, extend the
      // current subsequence
      else
      {
        subseq.push_back(e);
      }
 
      l = 0;
      r = subseq.size() - 1;
    }
  }
 
  // Return the answer
  return N - subseq.size();
}
 
// Driver code
int main()
{
  // Given arrays
  int A[] = {1, 2, 3, 4, 5};
  int B[] = {2, 5, 6, 4, 9, 12};
 
  int M = sizeof(A) /
          sizeof(A[0]);
  int N = sizeof(B) /
          sizeof(B[0]);
 
  // Function Call
  cout << minElements(A, B,
                      M, N);
 
  return 0;
}
 
// This code is contributed by divyeshrabadiya07

Java

// Java program for the above approach
 
import java.util.*;
import java.lang.*;
 
class GFG {
 
    // Function to return minimum element
    // to be added in array B so that array
    // A become subsequence of array B
    static int minElements(
        int[] A, int[] B, int N, int M)
    {
 
        // Stores indices of the
        // array elements
        Map<Integer, Integer> map
            = new HashMap<>();
 
        // Iterate over the array
        for (int i = 0;
             i < A.length; i++) {
 
            // Store the indices of
            // the array elements
            map.put(A[i], i);
        }
 
        // Stores the LIS
        ArrayList<Integer> subseq
            = new ArrayList<>();
 
        int l = 0, r = -1;
 
        for (int i = 0; i < M; i++) {
 
            // Check if element B[i]
            // is in array A[]
            if (map.containsKey(B[i])) {
 
                int e = map.get(B[i]);
 
                // Perform Binary Search
                while (l <= r) {
 
                    // Find the value of
                    // mid m
                    int m = l + (r - l) / 2;
 
                    // Update l and r
                    if (subseq.get(m) < e)
                        l = m + 1;
                    else
                        r = m - 1;
                }
 
                // If found better element
                // 'e' for pos r + 1
                if (r + 1 < subseq.size()) {
                    subseq.set(r + 1, e);
                }
 
                // Otherwise, extend the
                // current subsequence
                else {
                    subseq.add(e);
                }
 
                l = 0;
                r = subseq.size() - 1;
            }
        }
 
        // Return the answer
        return N - subseq.size();
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        // Given arrays
        int[] A = { 1, 2, 3, 4, 5 };
        int[] B = { 2, 5, 6, 4, 9, 12 };
 
        int M = A.length;
        int N = B.length;
 
        // Function Call
        System.out.println(
            minElements(A, B, M, N));
    }
}

Python3

# Python3 program for the above approach
 
# Function to return minimum element
# to be added in array B so that array
# A become subsequence of array B
def minElements(A, B, N, M):
     
    # Stores indices of the
    # array elements
    map = {}
 
    # Iterate over the array
    for i in range(len(A)):
 
        # Store the indices of
        # the array elements
        map[A[i]] = i
  
    # Stores the LIS
    subseq = []
 
    l = 0
    r = -1
 
    for i in range(M):
 
        # Check if element B[i]
        # is in array A[]
        if B[i] in map:
            e = map[B[i]]
 
            # Perform Binary Search
            while (l <= r):
 
                # Find the value of
                # mid m
                m = l + (r - l) // 2
 
                # Update l and r
                if (subseq[m] < e):
                    l = m + 1
                else:
                    r = m - 1
 
            # If found better element
            # 'e' for pos r + 1
            if (r + 1 < len(subseq)):
                subseq[r + 1]= e
 
            # Otherwise, extend the
            # current subsequence
            else:
                subseq.append(e)
 
            l = 0
            r = len(subseq) - 1
 
    # Return the answer
    return N - len(subseq)
 
# Driver Code
if __name__ == '__main__':
     
    # Given arrays
    A = [ 1, 2, 3, 4, 5 ]
    B = [ 2, 5, 6, 4, 9, 12 ]
 
    M = len(A)
    N = len(B)
 
    # Function call
    print(minElements(A, B, M, N))
 
# This code is contributed by mohit kumar 29

C#

// C# program for
// the above approach
using System;
using System.Collections.Generic;
class GFG{
 
// Function to return minimum element
// to be added in array B so that array
// A become subsequence of array B
static int minElements(int[] A, int[] B,
                       int N, int M)
{
  // Stores indices of the
  // array elements
  Dictionary<int,
             int> map = new Dictionary<int,
                                       int>();
   
  // Iterate over the array
  for (int i = 0;
           i < A.Length; i++)
  {
    // Store the indices of
    // the array elements
    map.Add(A[i], i);
  }
 
  // Stores the LIS
  List<int> subseq = new List<int>();
 
  int l = 0, r = -1;
 
  for (int i = 0; i < M; i++)
  {
    // Check if element B[i]
    // is in array []A
    if (map.ContainsKey(B[i]))
    {
      int e = map[B[i]];
 
      // Perform Binary Search
      while (l <= r)
      {
        // Find the value of
        // mid m
        int m = l + (r - l) / 2;
 
        // Update l and r
        if (subseq[m] < e)
          l = m + 1;
        else
          r = m - 1;
      }
 
      // If found better element
      // 'e' for pos r + 1
      if (r + 1 < subseq.Count)
      {
        subseq[r + 1] = e;
      }
 
      // Otherwise, extend the
      // current subsequence
      else
      {
        subseq.Add(e);
      }
 
      l = 0;
      r = subseq.Count - 1;
    }
  }
 
  // Return the answer
  return N - subseq.Count;
}
 
// Driver Code
public static void Main(String[] args)
{
  // Given arrays
  int[] A = {1, 2, 3, 4, 5};
  int[] B = {2, 5, 6, 4, 9, 12};
 
  int M = A.Length;
  int N = B.Length;
 
  // Function Call
  Console.WriteLine(minElements(A, B,
                                M, N));
}
}
 
// This code is contributed by Princi Singh

Javascript

<script>
// Javascript program for the
// above approach
 
// Function to return minimum
// element to be added in array
// B so that array A become
// subsequence of array B
function minElements(A, B, N, M)
{
  // Stores indices of the
  // array elements
  var map = new Map();
 
  // Iterate over the array
  for (var i = 0; i < N; i++)
  {
    // Store the indices of
    // the array elements
    map.set(A[i], i);
  }
 
  // Stores the LIS
  var subseq = [];
 
  var l = 0, r = -1;
 
  for (var i = 0; i < M; i++)
  {
    // Check if element B[i]
    // is in array A[]
    if (map.has(B[i]))
    {
      var e = map.get(B[i]);
 
      // Perform Binary Search
      while (l <= r)
      {
        // Find the value of
        // mid m
        var m = l + parseInt((r - l) / 2);
 
        // Update l and r
        if (subseq[m] < e)
          l = m + 1;
        else
          r = m - 1;
      }
 
      // If found better element
      // 'e' for pos r + 1
      if (r + 1 < subseq.length)
      {
        subseq[r + 1] = e;
      }
 
      // Otherwise, extend the
      // current subsequence
      else
      {
        subseq.push(e);
      }
 
      l = 0;
      r = subseq.length - 1;
    }
  }
 
  // Return the answer
  return N - subseq.length;
}
 
// Driver code
// Given arrays
var A = [1, 2, 3, 4, 5];
var B = [2, 5, 6, 4, 9, 12];
var M = A.length;
var N = B.length;
// Function Call
document.write( minElements(A, B,
                    M, N));
 
</script>

Producción:

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

Publicación traducida automáticamente

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

Minimice los elementos que se agregarán a una array dada de modo que contenga otra array dada como su subsecuencia | conjunto 2

C++

Java

Python3

C#

Javascript

Deja una respuesta Cancelar la respuesta