Dada una array arr[] que consta de N enteros y consultas de array 2D [][] que consta de Q consultas de la forma { p , x }, la tarea para cada consulta es reemplazar el elemento en la posición p con x e imprimir el recuento de distintos elementos presentes en el arreglo .
Ejemplos:
Entrada: Q = 3, arr[] = {2, 2, 5, 5, 4, 6, 3}, consultas[][] = {{1, 7}, {6, 8}, {7, 2} }
Salida: {6, 6, 5}
Explicación:
El total de elementos distintos después de cada consulta (indexación basada en uno): Consulta 1: p = 1 y x = 7. Por lo tanto, arr[1] = 7 y arr[] se convierte en {7, 2, 5, 5, 4, 6, 3}. Por lo tanto, elementos distintos = 6. Consulta 2: p = 6 y x = 8. Por lo tanto, arr[6] = 8 y arr[] se convierte en {7, 2, 5, 5, 4, 8, 3}. Por lo tanto, elementos distintos = 6. Consulta 3: p = 7 y x = 2. Por lo tanto, arr[7] = 2 y arr[] se convierte en {7, 2, 5, 5, 4, 8, 2}. Por lo tanto, elementos distintos = 5.Entrada: Q = 2, arr[] = {1, 1, 1, 1}, queries[][] = {{2, 2}, {3, 3}}
Salida: {2, 3}
Explicación:
El total elementos distintos después de cada consulta (indexación basada en uno): Consulta 1: p = 2 y x = 2. Por lo tanto, arr[2] = 2 y arr[] se convierte en {1, 2, 1, 1}. Por lo tanto, elementos distintos = 2. Consulta 2: p = 3 y x = 3. Por lo tanto, arr[3] = 3 y arr[] se convierte en {1, 2, 3, 1}. Por lo tanto, elementos distintos = 3.
Enfoque ingenuo: el enfoque más simple es actualizar la array dada para cada consulta e insertar todos los elementos de la array actualizada en un Set . Imprime el tamaño del conjunto como el conteo de distintos elementos del arreglo .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
#define R 3
#define C 2
// Function to the total
// number of distinct elements
// after each query update
void Distinct(int arr[], int n,
int p, int x)
{
// Update the array
arr[p - 1] = x;
// Store distinct elements
set<int> set;
for (int i = 0; i < n; i++)
{
set.insert(arr[i]);
}
// Print the size
cout << set.size() << " ";
}
// Function to print the count of
// distinct elements for each query
void updateArray(int arr[], int n,
int queries[R][C],
int q)
{
// Traverse the query
for (int i = 0; i < q; i++)
{
// Function Call to update
// each query
Distinct(arr, n,
queries[i][0],
queries[i][1]);
}
}
// Driver Code
int main()
{
// Given array arr[]
int arr[] = {2, 2, 5,
5, 4, 6, 3};
int N = sizeof(arr) /
sizeof(arr[0]);
int Q = 3;
// Given queries
int queries[R][C] = {{1, 7},
{6, 8},
{7, 2}};
// Function Call
updateArray(arr, N,
queries, Q);
}
// This code is contributed by gauravrajput1
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG {
// Function to the total number
// of distinct elements after each
// query update
static void Distinct(int arr[], int n,
int p, int x)
{
// Update the array
arr[p - 1] = x;
// Store distinct elements
Set<Integer> set = new HashSet<>();
for (int i = 0; i < n; i++) {
set.add(arr[i]);
}
// Print the size
System.out.print(set.size() + " ");
}
// Function to print the count of
// distinct elements for each query
static void updateArray(
int arr[], int n,
int queries[][], int q)
{
// Traverse the query
for (int i = 0; i < q; i++) {
// Function Call to update
// each query
Distinct(arr, n, queries[i][0],
queries[i][1]);
}
}
// Driver Code
public static void main(String[] args)
{
// Given array arr[]
int[] arr = { 2, 2, 5, 5, 4, 6, 3 };
int N = arr.length;
int Q = 3;
// Given queries
int queries[][]
= new int[][] { { 1, 7 },
{ 6, 8 },
{ 7, 2 } };
// Function Call
updateArray(arr, N, queries, Q);
}
}
Python3
# Python3 program for the # above approach # Function to the total number # of distinct elements after # each query update def Distinct(arr, n, p, x): # Update the array arr[p - 1] = x; # Store distinct elements s = set(); for i in range(n): s.add(arr[i]); # Print the size print(len(s), end = " "); # Function to print count # of distinct elements for # each query def updateArray(arr, n, queries, q): # Traverse the query for i in range(0, q): # Function Call to update # each query Distinct(arr, n, queries[i][0], queries[i][1]); # Driver Code if __name__ == '__main__': # Given array arr arr = [2, 2, 5, 5, 4, 6, 3]; N = len(arr); Q = 3; # Given queries queries = [[1, 7], [6, 8], [7, 2]]; # Function Call updateArray(arr, N, queries, Q); # This code is contributed by shikhasingrajput
C#
// C# program for the
// above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to the total number
// of distinct elements after each
// query update
static void Distinct(int []arr, int n,
int p, int x)
{
// Update the array
arr[p - 1] = x;
// Store distinct elements
HashSet<int> set =
new HashSet<int>();
for (int i = 0; i < n; i++)
{
set.Add(arr[i]);
}
// Print the size
Console.Write(set.Count + " ");
}
// Function to print the count of
// distinct elements for each query
static void updateArray(int []arr, int n,
int [,]queries, int q)
{
// Traverse the query
for (int i = 0; i < q; i++)
{
// Function Call to update
// each query
Distinct(arr, n, queries[i, 0],
queries[i, 1]);
}
}
// Driver Code
public static void Main(String[] args)
{
// Given array []arr
int[] arr = {2, 2, 5, 5,
4, 6, 3};
int N = arr.Length;
int Q = 3;
// Given queries
int [,]queries = new int[,] {{1, 7},
{6, 8},
{7, 2}};
// Function Call
updateArray(arr, N, queries, Q);
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
// Javascript Program to implement
// the above approach
var R = 3
var C = 2;
// Function to the total
// number of distinct elements
// after each query update
function Distinct(arr, n, p, x)
{
// Update the array
arr[p - 1] = x;
// Store distinct elements
var set = new Set();
for (var i = 0; i < n; i++)
{
set.add(arr[i]);
}
// Print the size
document.write( set.size + " ");
}
// Function to print the count of
// distinct elements for each query
function updateArray(arr, n, queries, q)
{
// Traverse the query
for (var i = 0; i < q; i++)
{
// Function Call to update
// each query
Distinct(arr, n,
queries[i][0],
queries[i][1]);
}
}
// Driver Code
// Given array arr[]
var arr = [2, 2, 5,
5, 4, 6, 3];
var N = arr.length;
var Q = 3;
// Given queries
var queries = [[1, 7],
[6, 8],
[7, 2]];
// Function Call
updateArray(arr, N,
queries, Q);
</script>
Producción
6 6 5
Complejidad temporal: O(Q*N)
Espacio auxiliar: O(N)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es almacenar la frecuencia de cada elemento de array en un mapa y luego recorrer cada consulta e imprimir el tamaño del mapa después de cada actualización. Siga los pasos a continuación para resolver el problema:
- Almacene la frecuencia de cada elemento en un Map M .
- Para cada consulta {p, x} , realice los siguientes pasos:
- Disminuya la frecuencia de arr[p] en 1 en el Mapa M . Si su frecuencia se reduce a 0 , elimina ese elemento del Mapa.
- Actualice arr[p] = x e incremente la frecuencia de x en 1 en el Mapa si ya está presente. De lo contrario, agregue el elemento x en el Mapa configurando su frecuencia como 1 .
- Para cada consulta en los pasos anteriores, imprima el tamaño del Mapa como el recuento de los distintos elementos de la array .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
#define Q 3
// Function to store the frequency
// of each element in the Map
void store(int arr[], int n,
map<int, int> &map)
{
for (int i = 0; i < n; i++)
{
// Store the frequency of
// element arr[i]
map[arr[i]]++;
}
}
// Function to update an array
// and map & to find the
// distinct elements
void Distinct(int arr[], int n,
int p, int x,
map<int, int> &map)
{
// Decrease the element
// if it was previously
// present in Map
map[arr[p - 1]] =
map[arr[p - 1]] - 1;
if (map[arr[p - 1]] == 0)
map.erase(arr[p - 1]);
// Add the new element
// to map
map[x]++;
// Update the array
arr[p - 1] = x;
// Print the count of
// distinct elements
cout << (map.size()) << " ";
}
// Function to count the distinct
// element after updating each query
static void updateQuery(int arr[], int n,
int queries[Q][2],
int q)
{
// Store the elements in map
map<int,int> map;
store(arr, n, map);
for (int i = 0; i < q; i++)
{
// Function Call
Distinct(arr, n,
queries[i][0],
queries[i][1], map);
}
}
// Driver Code
int main()
{
// Given array arr[]
int arr[] = {2, 2, 5,
5, 4, 6, 3};
int N = sizeof(arr) /
sizeof(arr[0]);
// Given Queries
int queries[Q][2] = {{1, 7},
{6, 8},
{7, 2}};
// Function Call
updateQuery(arr, N, queries, Q);
}
// This code is contributed by gauravrajput1
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG {
// Function to store the frequency
// of each element in the Map
static void store(int arr[], int n,
HashMap<Integer,
Integer>
map)
{
for (int i = 0; i < n; i++) {
// Store the frequency of
// element arr[i]
if (!map.containsKey(arr[i]))
map.put(arr[i], 1);
else
map.put(arr[i],
map.get(arr[i]) + 1);
}
}
// Function to update an array and
// map & to find the distinct elements
static void Distinct(int arr[], int n,
int p, int x,
HashMap<Integer,
Integer>
map)
{
// Decrease the element if it
// was previously present in Map
map.put(arr[p - 1],
map.get(arr[p - 1]) - 1);
if (map.get(arr[p - 1]) == 0)
map.remove(arr[p - 1]);
// Add the new element to map
if (!map.containsKey(x)) {
map.put(x, 1);
}
else {
map.put(x, map.get(x) + 1);
}
// Update the array
arr[p - 1] = x;
// Print the count of distinct
// elements
System.out.print(map.size() + " ");
}
// Function to count the distinct
// element after updating each query
static void updateQuery(
int arr[], int n,
int queries[][], int q)
{
// Store the elements in map
HashMap<Integer, Integer> map
= new HashMap<>();
store(arr, n, map);
for (int i = 0; i < q; i++) {
// Function Call
Distinct(arr, n, queries[i][0],
queries[i][1], map);
}
}
// Driver Code
public static void main(String[] args)
{
// Given array arr[]
int[] arr = { 2, 2, 5, 5, 4, 6, 3 };
int N = arr.length;
int Q = 3;
// Given Queries
int queries[][]
= new int[][] { { 1, 7 },
{ 6, 8 },
{ 7, 2 } };
// Function Call
updateQuery(arr, N, queries, Q);
}
}
Python3
# Python3 Program to implement
# the above approach
# Function to store the frequency
# of each element in the Map
def store(arr, n, Map) :
for i in range(n) :
# Store the frequency of
# element arr[i]
if (arr[i] not in Map) :
Map[arr[i]] = 1
else :
Map[arr[i]] += 1
# Function to update an array and
# map & to find the distinct elements
def Distinct(arr, n, p, x, Map) :
# Decrease the element if it
# was previously present in Map
Map[arr[p - 1]] = Map[arr[p - 1]] - 1
if (Map[arr[p - 1]] == 0) :
del Map[arr[p - 1]]
# Add the new element to map
if(x not in Map) :
Map[x] = 1
else :
Map[x] += 1
# Update the array
arr[p - 1] = x
# Print the count of distinct
# elements
print(len(Map), end = " ")
# Function to count the distinct
# element after updating each query
def updateQuery(arr, n, queries, q) :
# Store the elements in map
Map = {}
store(arr, n, Map)
for i in range(q) :
# Function Call
Distinct(arr, n, queries[i][0], queries[i][1], Map)
# Given array []arr
arr = [ 2, 2, 5, 5, 4, 6, 3 ]
N = len(arr)
Q = 3
# Given queries
queries = [ [ 1, 7 ], [ 6, 8 ], [ 7, 2 ] ]
# Function call
updateQuery(arr, N, queries, Q)
# This code is contributed by divyesh072019.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to store the frequency
// of each element in the Map
static void store(int []arr, int n,
Dictionary<int, int>map)
{
for(int i = 0; i < n; i++)
{
// Store the frequency of
// element arr[i]
if (!map.ContainsKey(arr[i]))
map.Add(arr[i], 1);
else
map[arr[i]] = map[arr[i]] + 1;
}
}
// Function to update an array and
// map & to find the distinct elements
static void Distinct(int []arr, int n,
int p, int x,
Dictionary<int, int>map)
{
// Decrease the element if it
// was previously present in Map
map[arr[p - 1]] = map[arr[p - 1]] - 1;
if (map[arr[p - 1]] == 0)
map.Remove(arr[p - 1]);
// Add the new element to map
if (!map.ContainsKey(x))
{
map.Add(x, 1);
}
else
{
map[x]= map[x] + 1;
}
// Update the array
arr[p - 1] = x;
// Print the count of distinct
// elements
Console.Write(map.Count + " ");
}
// Function to count the distinct
// element after updating each query
static void updateQuery(int []arr, int n,
int [,]queries, int q)
{
// Store the elements in map
Dictionary<int,
int> map = new Dictionary<int,
int>();
store(arr, n, map);
for(int i = 0; i < q; i++)
{
// Function Call
Distinct(arr, n, queries[i, 0],
queries[i, 1], map);
}
}
// Driver Code
public static void Main(String[] args)
{
// Given array []arr
int[] arr = { 2, 2, 5, 5, 4, 6, 3 };
int N = arr.Length;
int Q = 3;
// Given queries
int [,]queries = new int[,]{ { 1, 7 },
{ 6, 8 },
{ 7, 2 } };
// Function call
updateQuery(arr, N, queries, Q);
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// Javascript program for the above approach
// Function to store the frequency
// of each element in the Map
function store(arr,n,map)
{
for (let i = 0; i < n; i++) {
// Store the frequency of
// element arr[i]
if (!map.has(arr[i]))
map.set(arr[i], 1);
else
map.set(arr[i],
map.get(arr[i]) + 1);
}
}
// Function to update an array and
// map & to find the distinct elements
function Distinct(arr,n,p,x,map)
{
// Decrease the element if it
// was previously present in Map
map.set(arr[p - 1],
map.get(arr[p - 1]) - 1);
if (map.get(arr[p - 1]) == 0)
map.delete(arr[p - 1]);
// Add the new element to map
if (!map.has(x)) {
map.set(x, 1);
}
else {
map.set(x, map.get(x) + 1);
}
// Update the array
arr[p - 1] = x;
// Print the count of distinct
// elements
document.write(map.size + " ");
}
// Function to count the distinct
// element after updating each query
function updateQuery(arr,n,queries,q)
{
// Store the elements in map
let map
= new Map();
store(arr, n, map);
for (let i = 0; i < q; i++) {
// Function Call
Distinct(arr, n, queries[i][0],
queries[i][1], map);
}
}
// Driver Code
let arr=[2, 2, 5, 5, 4, 6, 3];
let N = arr.length;
let Q = 3;
let queries=[[ 1, 7 ],[ 6, 8 ],[ 7, 2 ]];
// Function Call
updateQuery(arr, N, queries, Q);
// This code is contributed by patel2127
</script>
Producción
6 6 5
Complejidad temporal: O(N + Q)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por ayush_dragneel y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA