Suma de array después de reemplazar todas las apariciones de X por Y para consultas Q

Dada una array de enteros arr[] y consultas Q , la tarea es encontrar la suma de la array para cada consulta del siguiente tipo: 

  • Cada consulta contiene 2 enteros X e Y , donde todas las apariciones de X en arr[] deben reemplazarse por Y .
  • Después de cada consulta, imprimen la suma de la array.

Ejemplos:

Entrada: arr[] = { 1, 2, 1, 3, 2}, X[] = { 2, 3, 5 }, Y[] = { 3, 1, 2 } 
Salida: 11 5 5 
Explicación: 
Después de la Primera consulta, reemplace 2 con 3, arr[] = { 1, 3, 1, 3, 3 }, Sum = 11. 
Después de la segunda consulta, reemplace 3 con 1, arr[] = { 1, 1, 1, 1 , 1 }, Sum = 5. 
Después de la tercera consulta, reemplace 5 con 2, arr[] = { 1, 1, 1, 1, 1 }, Sum = 5. 

Entrada: arr[] = { 12, 22, 11, 11, 2}, X[] = {2, 11, 22}, Y[] = {12, 222, 2} 
Salida: 68 490 470 

Enfoque ingenuo: 
el enfoque más simple para resolver el problema mencionado anteriormente es atravesar la array y reemplazar todas las instancias de X con Y para cada consulta y calcular la suma. 

Complejidad de tiempo: O(N * Q)

Enfoque eficiente: 
para optimizar el método anterior, siga los pasos que se indican a continuación: 

  • Calcule previamente y almacene la suma de la array en una variable S y almacene las frecuencias de los elementos de la array en un conteo de mapas .
  • Luego, haga lo siguiente para cada consulta: 
    • Encuentre la frecuencia de X almacenada en el mapa.
    • Restar X * cuenta[X] de S .
    • Establezca count[Y] = count[X] y luego count[X] = 0 .
    • Agregue Y * cuenta[Y] a S .
    • Imprime el valor actualizado de S .

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

C++

// C++ implementation to find the sum
// of the array for the given Q queries
 
#include <bits/stdc++.h>
using namespace std;
 
// Function that print the sum of
// the array for Q queries
void sumOfTheArrayForQuery(int* A, int N,
                           int* X, int* Y,
                           int Q)
{
    int sum = 0;
 
    // Stores the frequencies
    // of array elements
    unordered_map<int, int> count;
 
    // Calculate the sum of
    // the initial array and
    // store the frequency of
    // each element in map
 
    for (int i = 0; i < N; i++) {
        sum += A[i];
        count[A[i]]++;
    }
 
    // Iterate for all the queries
 
    for (int i = 0; i < Q; i++) {
        // Store query values
        int x = X[i], y = Y[i];
 
        // Decrement the sum accordingly
        sum -= count[X[i]] * X[i];
 
        // Increment the sum accordingly
        sum += count[X[i]] * Y[i];
 
        // Set count of Y[i]
        count[Y[i]] += count[X[i]];
 
        // Reset count of X[i]
        count[X[i]] = 0;
 
        // Print the sum
        cout << sum << " ";
    }
}
 
// Driver Code
int main()
{
    int arr[] = { 1, 2, 1, 3, 2 };
    int X[] = { 2, 3, 5 };
    int Y[] = { 3, 1, 2 };
 
    int N = sizeof(arr) / sizeof(arr[0]);
 
    int Q = sizeof(X) / sizeof(X[0]);
 
    // Function call
    sumOfTheArrayForQuery(arr, N, X, Y, Q);
 
    return 0;
}

Java

// Java implementation to
// find the sum of the array
// for the given Q queries
import java.util.*;
class GFG{
   
// Function that print the sum of
// the array for Q queries
public static void sumOfTheArrayForQuery(int[] A, int N,
                                         int[] X, int[] Y,
                                         int Q)
{
  int sum = 0;
 
  // Stores the frequencies
  // of array elements
  // Create an empty hash map
  HashMap<Integer,
          Integer> count = new HashMap<>();
 
  // Calculate the sum of
  // the initial array and
  // store the frequency of
  // each element in map
  for (int i = 0; i < N; i++)
  {
    sum += A[i];
    if (count.containsKey(A[i]))
    {
      count.replace(A[i],
      count.get(A[i]) + 1);
    }
    else
    {
      count.put(A[i], 1);
    }
  }
 
  // Iterate for all the queries
  for (int i = 0; i < Q; i++)
  {
    // Store query values
    int x = X[i], y = Y[i];
 
    if(count.containsKey(X[i]))
    {
      // Decrement the sum accordingly
      sum -= count.get(X[i]) * X[i];
      // Increment the sum accordingly
      sum += count.get(X[i]) * Y[i];
    }
 
    // Set count of Y[i]
    if(count.containsKey(Y[i]) &&
       count.containsKey(X[i]))
    {
      count.replace(Y[i],
      count.get(Y[i]) +
      count.get(X[i]));
    }
 
    // Reset count of X[i]
    if(count.containsKey(X[i]))
    {
      count.replace(X[i], 0);
    }
 
    // Print the sum
    System.out.print(sum + " ");
  }
}
 
// Driver code
public static void main(String[] args)
{
  int arr[] = {1, 2, 1, 3, 2};
  int X[] = {2, 3, 5};
  int Y[] = {3, 1, 2};
 
  int N = arr.length;
  int Q = X.length;
 
  // Function call
  sumOfTheArrayForQuery(arr, N,
                        X, Y, Q);
}
}
 
// This code is contributed by divyeshrabadiya07

Python3

# Python3 implementation to find the sum
# of the array for the given Q queries
 
# Function that print the sum of
# the array for Q queries
def sumOfTheArrayForQuery(A, N, X, Y, Q):
     
    sum = 0
 
    # Stores the frequencies
    # of array elements
    count = {}
 
    # Calculate the sum of
    # the initial array and
    # store the frequency of
    # each element in map
    for i in range(N):
        sum += A[i]
         
        if A[i] in count:
            count[A[i]] += 1
        else:
            count[A[i]] = 1
 
    # Iterate for all the queries
    for i in range(Q):
 
        # Store query values
        x = X[i]
        y = Y[i]
         
        if X[i] not in count:
            count[X[i]] = 0
        if Y[i] not in count:
            count[Y[i]] = 0
 
        # Decrement the sum accordingly
        sum -= (count[X[i]] * X[i])
 
        # Increment the sum accordingly
        sum += count[X[i]] * Y[i]
 
        # Set count of Y[i]
        count[Y[i]] += count[X[i]]
 
        # Reset count of X[i]
        count[X[i]] = 0
 
        # Print the sum
        print(sum, end = " ")
 
# Driver Code
arr = [ 1, 2, 1, 3, 2, ]
X = [ 2, 3, 5 ]
Y = [ 3, 1, 2 ]
N = len(arr)
Q = len(X)
 
# Function call
sumOfTheArrayForQuery(arr, N, X, Y, Q)
 
# This code is contributed by avanitrachhadiya2155

C#

// C# implementation to
// find the sum of the array
// for the given Q queries
using System;
using System.Collections.Generic;
class GFG{
   
// Function that print the sum of
// the array for Q queries
public static void sumOfTheArrayForQuery(int[] A, int N,
                                         int[] X, int[] Y,
                                         int Q)
{
  int sum = 0;
 
  // Stores the frequencies
  // of array elements
  // Create an empty hash map
  Dictionary<int,
             int> count = new Dictionary<int,
                                         int>();
 
  // Calculate the sum of
  // the initial array and
  // store the frequency of
  // each element in map
  for (int i = 0; i < N; i++)
  {
    sum += A[i];
    if (count.ContainsKey(A[i]))
    {
      count[A[i]]= count[A[i]] + 1;
    }
    else
    {
      count.Add(A[i], 1);
    }
  }
 
  // Iterate for all the queries
  for (int i = 0; i < Q; i++)
  {
    // Store query values
    int x = X[i], y = Y[i];
 
    if(count.ContainsKey(X[i]))
    {
      // Decrement the sum accordingly
      sum -= count[X[i]] * X[i];
      // Increment the sum accordingly
      sum += count[X[i]] * Y[i];
    }
 
    // Set count of Y[i]
    if(count.ContainsKey(Y[i]) &&
       count.ContainsKey(X[i]))
    {
      count[Y[i]] = count[Y[i]] +
                    count[X[i]];
    }
 
    // Reset count of X[i]
    if(count.ContainsKey(X[i]))
    {
      count[X[i]] = 0;
    }
 
    // Print the sum
    Console.Write(sum + " ");
  }
}
 
// Driver code
public static void Main(String[] args)
{
  int []arr = {1, 2, 1, 3, 2};
  int []X = {2, 3, 5};
  int []Y = {3, 1, 2};
 
  int N = arr.Length;
  int Q = X.Length;
 
  // Function call
  sumOfTheArrayForQuery(arr, N,
                        X, Y, Q);
}
}
 
// This code is contributed by Amit Katiyar

Javascript

<script>
 
 
// Javascript implementation to find the sum
// of the array for the given Q queries
 
// Function that print the sum of
// the array for Q queries
function sumOfTheArrayForQuery(A, N, X, Y, Q)
{
    var sum = 0;
 
    // Stores the frequencies
    // of array elements
    var count = new Map();
 
    // Calculate the sum of
    // the initial array and
    // store the frequency of
    // each element in map
 
    for (var i = 0; i < N; i++) {
        sum += A[i];
        if(count.has(A[i]))
            count.set(A[i], count.get(A[i])+1)
        else
            count.set(A[i], 1)
    }
 
    // Iterate for all the queries
 
    for (var i = 0; i < Q; i++) {
        // Store query values
        var x = X[i], y = Y[i];
 
        if(count.has(X[i]))
        {
            // Decrement the sum accordingly
            sum -= count.get(X[i]) * X[i];
 
                // Increment the sum accordingly
            sum += count.get(X[i]) * Y[i];
        }
 
        if(count.has(Y[i]))
        {
            // Set count of Y[i]
            count.set(Y[i], count.get(Y[i]) + count.get(X[i]));
        }
 
        // Reset count of X[i]
        count.set(X[i] , 0);
 
        // Print the sum
        document.write( sum + " ");
    }
}
 
// Driver Code
var arr = [1, 2, 1, 3, 2];
var X = [2, 3, 5 ];
var Y = [3, 1, 2 ];
var N = arr.length;
var Q = X.length;
// Function call
sumOfTheArrayForQuery(arr, N, X, Y, Q);
 
 
</script>
Producción: 

11 5 5

 

Complejidad temporal: O(N), ya que cada consulta tiene una complejidad computacional de O(1). 
Espacio Auxiliar: O(N)

Publicación traducida automáticamente

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