Dada una array arr[] que consta de N enteros, lea cada elemento de la array uno por uno y realice las siguientes operaciones:
- Si el elemento actual arr[i] había aparecido previamente en la array, aumente su primera aparición en K .
- De lo contrario, inserte arr[i] en la secuencia
La tarea es imprimir la secuencia final de enteros obtenidos al realizar las operaciones anteriores.
Ejemplos:
Entrada: arr[] = {1, 2, 3, 2, 3}, K = 1
Salida: [1, 4, 3, 2, 3]
Explicación:Llegada: 1
Dado que 1 es el primer elemento de la secuencia, simplemente insértelo en la solución.
Por lo tanto, b[] = [1]Llegada: 2
Dado que 2 no existe en la array, simplemente insértelo en la solución.
Por lo tanto, b[] = [1, 2]Llegada: 3
Dado que 3 no existe en la array, simplemente insértelo en la solución.
Por lo tanto, b[] = [1, 2, 3]Llegada: 2
Dado que 2 ya existe, aumentar su primera aparición en K(=1) modifica el arreglo b[] a [1, 3, 3, 2]Llegada: 3
Dado que 3 ya existe, aumentar su primera aparición en K(=1) modifica el arreglo b[] a [1, 4, 3, 2, 3]Entrada: arr[] = {1, 4, 1, 1, 4}, K = 6
Salida : [7, 10, 7, 1, 4]
Enfoque ingenuo: el enfoque más simple para resolver el problema es recorrer la array, y para cada elemento de la array arr[i] , recorrer el rango [0, i – 1] para verificar si arr[i] ya está presente en la array O no. Si se determina que es cierto, aumente la primera aparición de arr[i] en K .
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar utilizando Hashing . Siga los pasos a continuación para resolver el problema:
- Recorra la array y almacene la ocurrencia de cada elemento de la array en un mapa emparejado con el índice de su ocurrencia en orden creciente.
- Si se encuentra que arr[i] ya está presente en el Mapa , elimine la primera aparición de arr[i ] del Mapa . Inserte ese índice emparejado con arr[i] + K como la clave de nuevo en Map .
- Repita los pasos anteriores para todos los elementos de la array. Una vez recorrida toda la array, obtenga la secuencia de enteros del Mapa e imprima la secuencia final.
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;
// Print the required final sequence
void printSequence(vector<int>& A,
int n, int k)
{
// Stores the array element-index pairs
unordered_map<int, set<int> > mp;
// Stores the required sequence
vector<int> sol;
// Insert all array elements
for (int x : A)
sol.push_back(x);
for (int i = 0; i < n; i++) {
// If current element has
// not occurred previously
if (mp.find(sol[i]) == mp.end()
|| mp[sol[i]].size() == 0) {
mp[sol[i]].insert(i);
}
// Otherwise
else {
// Iterator to the first index
// containing sol[i]
auto idxx = mp[sol[i]].begin();
int idx = *idxx;
// Remove that occurrence
mp[sol[i]].erase(idxx);
// Increment by K
sol[idx] += k;
// Insert the incremented
// element at that index
mp[sol[idx]].insert(idx);
mp[sol[i]].insert(i);
}
}
// Print the final sequence
for (int x : sol) {
cout << x << " ";
}
}
// Driver Code
int main()
{
int N = 5;
int K = 6;
vector<int> A = { 1, 4, 1, 1, 4 };
printSequence(A, N, K);
}
Java
// Java Program to implement the above approach
import java.util.*;
public class Main {
// Driver Code
public static void main(String[] args)
{
int N = 5;
int K = 6;
int[] A = { 1, 4, 1, 1, 4 };
printSequence(A, N, K);
}
// Print the required final sequence
public static void printSequence(int[] A, int n, int k)
{
// Stores the array element-index pairs
HashMap<Integer, ArrayList<Integer> > mp
= new HashMap<>();
// Stores the required sequence
ArrayList<Integer> sol = new ArrayList<>();
// Insert all array elements
for (int x : A) {
sol.add(x);
}
for (int i = 0; i < n; i++) {
// If current element has
// not occurred previously
if (!mp.containsKey(sol.get(i))
|| mp.get(sol.get(i)).size() == 0) {
mp.put(sol.get(i),
new ArrayList<>(Arrays.asList(i)));
}
// Otherwise
else {
// first index containing sol[i]
int idx = mp.get(sol.get(i)).get(0);
// Remove that occurrence
mp.get(sol.get(i)).remove((Integer)idx);
// Increment by K
sol.set(idx, sol.get(idx) + k);
// Insert the incremented
// element at that index
mp.putIfAbsent(
sol.get(idx),
new ArrayList<>(Arrays.asList()));
mp.get(sol.get(idx)).add((Integer)idx);
mp.putIfAbsent(
sol.get(i),
new ArrayList<>(Arrays.asList()));
mp.get(sol.get(i)).add((Integer)i);
}
}
// Print the final sequence
for (int x : sol) {
System.out.print(x + " ");
}
}
}
// This code is contributed by Tapesh (tapeshdua420)
Javascript
<script>
// Javascript program to implement
// the above approach
// Print the required final sequence
function printSequence(A, n, k)
{
// Stores the array element-index pairs
var mp = new Map();
// Stores the required sequence
var sol = [];
// Insert all array elements
A.forEach(x => {
sol.push(x);
});
for(var i = 0; i < n; i++)
{
// If current element has
// not occurred previously
if (!mp.has(sol[i]) ||
mp.get(sol[i]).size == 0)
{
var tmp = new Set();
tmp.add(i)
mp.set(sol[i],tmp)
}
// Otherwise
else
{
// Iterator to the first index
// containing sol[i]
var idxx = [...mp.get(sol[i])].sort(
(a, b) => a - b)[0];
var idx = idxx;
// Remove that occurrence
var x = mp.get(sol[i]);
x.delete(idxx);
mp.set(sol[i], x);
// Increment by K
sol[idx] += k;
// Insert the incremented
// element at that index
if (!mp.has(sol[idx]))
mp.set(sol[idx], new Set())
x = mp.get(sol[idx]);
x.add(idx);
mp.set(sol[idx], x);
x = mp.get(sol[i]);
x.add(i);
mp.set(sol[i], x);
}
}
// Print the final sequence
sol.forEach(x => {
document.write(x + " ");
});
}
// Driver Code
var N = 5;
var K = 6;
var A = [ 1, 4, 1, 1, 4 ];
printSequence(A, N, K);
// This code is contributed by importantly
</script>
7 10 7 1 4
Complejidad temporal: O(NlogN)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por Ripunjoy Medhi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA