Minimice las inserciones y eliminaciones en la array A[] dada para que sea idéntica a la array B[]

Dadas dos arrays A[] y B[] de longitud N y M respectivamente, la tarea es encontrar el número mínimo de inserciones y eliminaciones en la array A[] , necesarias para que ambas arrays sean idénticas.
Nota: la array B[] está ordenada y todos sus elementos son distintos, las operaciones se pueden realizar en cualquier índice, no necesariamente al final.

Ejemplo:

Entrada: A[] = {1, 2, 5, 3, 1}, B[] = {1, 3, 5}
Salida: 4 
Explicación: En la primera operación, elimine A[1] de la array A[] y en 2da operación, inserte 3 en esa posición. En la 3ra y 4ta operación, borre A[3] y A[4]. Por lo tanto, A[] = {1, 3, 5} = B[] en 4 operaciones que es el mínimo posible.

Entrada: A[] = {1, 4}, B[] = {1, 4}
Salida: 0

Enfoque: el problema dado se puede resolver observando el hecho de que la elección más óptima de elementos que no se deben eliminar de la array A[] son ​​los elementos de la subsecuencia creciente más larga entre los elementos comunes en A[] y B[] . Por lo tanto, el problema anterior se puede resolver almacenando los elementos comunes de la array A[] y B[] en un vector y encontrando el LIS usando este algoritmo. A partir de entonces, todos los elementos que no sean LIS se pueden eliminar de A[] y los elementos restantes que están en B[] pero no en A[]se puede insertar

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

// C++ program of the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find minimum operations
// to convert array A to B using
// insertions and deletion opertations
int minInsAndDel(int A[], int B[], int n, int m)
{
 
    // Stores the common elements in A and B
    vector<int> common;
    unordered_set<int> s;
 
    // Loop to iterate over B
    for (int i = 0; i < m; i++) {
        s.insert(B[i]);
    }
 
    // Loop to iterate over A
    for (int i = 0; i < n; i++) {
 
        // If current element is also present
        // in array B
        if (s.find(A[i]) != s.end()) {
            common.push_back(A[i]);
        }
    }
 
    // Stores the Longest Increasing Subsequence
    // among the common elements in A and B
    vector<int> lis;
 
    // Loop to find the LIS among the common
    // elements in A and B
    for (auto e : common) {
        auto it = lower_bound(
            lis.begin(), lis.end(), e);
 
        if (it != lis.end())
            *it = e;
        else
            lis.push_back(e);
    }
 
    // Stores the final answer
    int ans;
 
    // Count of elements to be inserted in A[]
    ans = m - lis.size();
 
    // Count of elements to be deleted from A[]
    ans += n - lis.size();
 
    // Return Answer
    return ans;
}
 
// Driver Code
int main()
{
    int N = 5, M = 3;
    int A[] = { 1, 2, 5, 3, 1 };
    int B[] = { 1, 3, 5 };
 
    cout << minInsAndDel(A, B, N, M) << endl;
 
    return 0;
}

/*package whatever //do not write package name here */
import java.util.*;
 
class GFG
{
   
  // Function to implement lower_bound
static int lower_bound(int arr[], int X)
{
    int mid;
    int N = arr.length;
   
    // Initialise starting index and
    // ending index
    int low = 0;
    int high = N;
  
    // Till low is less than high
    while (low < high) {
        mid = low + (high - low) / 2;
  
        // If X is less than or equal
        // to arr[mid], then find in
        // left subarray
        if (X <= arr[mid]) {
            high = mid;
        }
  
        // If X is greater arr[mid]
        // then find in right subarray
        else {
            low = mid + 1;
        }
    }
    
    // if X is greater than arr[n-1]
    if(low < N && arr[low] < X) {
       low++;
    }
        
    // Return the lower_bound index
    return low;
}
  
    // Function to find minimum operations
    // to convert array A to B using
    // insertions and deletion opertations
    static int minInsAndDel(int A[], int B[], int n, int m)
    {
 
        // Stores the common elements in A and B
        int[] common = new int[n];
        int k = 0;
        HashSet<Integer> s= new HashSet<Integer>();
 
        // Loop to iterate over B
        for (int i = 0; i < m; i++) {
            s.add(B[i]);
        }
 
        // Loop to iterate over A
        for (int i = 0; i < n; i++) {
 
            // If current element is also present
            // in array B
            if (s.contains(A[i]) == false) {
                common[k++] = A[i];
            }
        }
 
        // Stores the Longest Increasing Subsequence
        // among the common elements in A and B
        int[] lis = new int[n];
        k = 0;
      ArrayList<Integer> LIS = new ArrayList<Integer>();
       
        // Loop to find the LIS among the common
        // elements in A and B
        for (int e : common) {
            int it = lower_bound(lis, e);
 
            if (it <lis.length)
                it = e;
            else{
                lis[k++] = e;
                LIS.add(e);
            }
        }
 
        // Stores the final answer
        int ans;
 
        // Count of elements to be inserted in A[]
        ans = m - LIS.size()-1;
 
        // Count of elements to be deleted from A[]
        ans = ans+ n - LIS.size()-1;
 
        // Return Answer
        return ans;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int N = 5, M = 3;
        int A[] = { 1, 2, 5, 3, 1 };
        int B[] = { 1, 3, 5 };
 
        System.out.println(minInsAndDel(A, B, N, M));
    }
}
 
// This code is contributed by lokeshpotta20.

# python program of the above approach
from bisect import bisect_left
 
# Function to find minimum operations
# to convert array A to B using
# insertions and deletion opertations
def minInsAndDel(A, B, n, m):
 
    # Stores the common elements in A and B
    common = []
    s = set()
 
    # Loop to iterate over B
    for i in range(0, m):
        s.add(B[i])
 
    # Loop to iterate over A
    for i in range(0, n):
 
        # If current element is also present
        # in array B
        if (A[i] in s):
            common.append(A[i])
 
    # Stores the Longest Increasing Subsequence
    # among the common elements in A and B
    lis = []
 
    # Loop to find the LIS among the common
    # elements in A and B
    for e in common:
        it = bisect_left(lis, e, 0, len(lis))
 
        if (it != len(lis)):
            lis[it] = e
        else:
            lis.append(e)
 
    # Stores the final answer
    ans = 0
 
    # Count of elements to be inserted in A[]
    ans = m - len(lis)
 
    # Count of elements to be deleted from A[]
    ans += n - len(lis)
 
    # Return Answer
    return ans
 
# Driver Code
if __name__ == "__main__":
 
    N = 5
    M = 3
    A = [1, 2, 5, 3, 1]
    B = [1, 3, 5]
 
    print(minInsAndDel(A, B, N, M))
 
    # This code is contributed by rakeshsahni

/*package whatever //do not write package name here */
using System;
using System.Collections.Generic;
 
class GFG {
 
    // Function to implement lower_bound
    static int lower_bound(int[] arr, int X)
    {
        int mid;
        int N = arr.Length;
 
        // Initialise starting index and
        // ending index
        int low = 0;
        int high = N;
 
        // Till low is less than high
        while (low < high) {
            mid = low + (high - low) / 2;
 
            // If X is less than or equal
            // to arr[mid], then find in
            // left subarray
            if (X <= arr[mid]) {
                high = mid;
            }
 
            // If X is greater arr[mid]
            // then find in right subarray
            else {
                low = mid + 1;
            }
        }
 
        // if X is greater than arr[n-1]
        if (low < N && arr[low] < X) {
            low++;
        }
 
        // Return the lower_bound index
        return low;
    }
 
    // Function to find minimum operations
    // to convert array A to B using
    // insertions and deletion opertations
    static int minInsAndDel(int[] A, int[] B, int n, int m)
    {
 
        // Stores the common elements in A and B
        int[] common = new int[n];
        int k = 0;
        HashSet<int> s = new HashSet<int>();
 
        // Loop to iterate over B
        for (int i = 0; i < m; i++) {
            s.Add(B[i]);
        }
 
        // Loop to iterate over A
        for (int i = 0; i < n; i++) {
 
            // If current element is also present
            // in array B
            if (s.Contains(A[i]) == false) {
                common[k++] = A[i];
            }
        }
 
        // Stores the Longest Increasing Subsequence
        // among the common elements in A and B
        int[] lis = new int[n];
        k = 0;
        List<int> LIS = new List<int>();
 
        // Loop to find the LIS among the common
        // elements in A and B
        foreach(int e in common)
        {
            int it = lower_bound(lis, e);
 
            if (it < lis.Length)
                it = e;
            else {
                lis[k++] = e;
                LIS.Add(e);
            }
        }
 
        // Stores the final answer
        int ans;
 
        // Count of elements to be inserted in A[]
        ans = m - LIS.Count - 1;
 
        // Count of elements to be deleted from A[]
        ans = ans + n - LIS.Count - 1;
 
        // Return Answer
        return ans;
    }
 
    // Driver Code
    public static void Main(string[] args)
    {
        int N = 5, M = 3;
        int[] A = { 1, 2, 5, 3, 1 };
        int[] B = { 1, 3, 5 };
 
        Console.WriteLine(minInsAndDel(A, B, N, M));
    }
}
 
// This code is contributed by ukasp.

<script>
// Javascript program of the above approach
 
// Function to find minimum operations
// to convert array A to B using
// insertions and deletion opertations
function minInsAndDel(A, B, n, m) {
 
  // Stores the common elements in A and B
  let common = [];
  let s = new Set();
 
  // Loop to iterate over B
  for (let i = 0; i < m; i++) {
    s.add(B[i]);
  }
 
  // Loop to iterate over A
  for (let i = 0; i < n; i++) {
 
    // If current element is also present
    // in array B
    if (s.has(A[i])) {
      common.push(A[i]);
    }
  }
 
  // Stores the Longest Increasing Subsequence
  // among the common elements in A and B
  let lis = [];
 
  // Loop to find the LIS among the common
  // elements in A and B
  for (e of common) {
    let it = lower_bound(lis, lis.length, e);
 
    if (lis.includes(it))
      it = e;
    else
      lis.push(e);
  }
 
  // Stores the final answer
  let ans;
 
  // Count of elements to be inserted in A[]
  ans = m - lis.length;
 
  // Count of elements to be deleted from A[]
  ans += n - lis.length;
 
  // Return Answer
  return ans;
}
 
 
function lower_bound(arr, N, X)
{
    let mid;
 
    // Initialise starting index and
    // ending index
    let low = 0;
    let high = N;
 
  // Till low is less than high
  while (low < high) {
    mid = Math.floor(low + (high - low) / 2);
 
    // If X is less than or equal
    // to arr[mid], then find in
    // left subarray
    if (X <= arr[mid]) {
      high = mid;
    }
 
    // If X is greater arr[mid]
    // then find in right subarray
    else {
      low = mid + 1;
    }
  }
 
  // if X is greater than arr[n-1]
  if (low < N && arr[low] < X) {
    low++;
  }
 
  // Return the lower_bound index
  return low;
}
 
 
// Driver Code
let N = 5, M = 3;
let A = [1, 2, 5, 3, 1];
let B = [1, 3, 5];
 
document.write(minInsAndDel(A, B, N, M));
 
// This code is contributed by saurabh_jaiswal.
</script>

4

Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(N)