Dado un entero M que representa una array que inicialmente tiene números del 1 al M. También se proporciona una array de consulta . Para cada consulta, busque el número en la array inicial y llévelo al frente de la array. La tarea es devolver los índices del elemento buscado en la array dada para cada consulta.
Ejemplos:
Entrada: Q[] = {3, 1, 2, 1}, M = 5
Salida: [2, 1, 2, 1]
Explicaciones:
Dado que m = 5, la array inicial es [1, 2, 3, 4, 5 ].
Consulta 1: busque 3 en [1, 2, 3, 4, 5] y muévalo al principio. Después de moverse, la array se ve como [3, 1, 2, 4, 5]. 3 está en el índice 2.
Consulta 2: mueva 1 de [3, 1, 2, 4, 5] al comienzo de la array para que la array se vea como [1, 3, 2, 4, 5]. 1 está presente en el índice 1.
Consulta 3: mueva 2 de [1, 3, 2, 4, 5] al comienzo de la array para que la array se vea como [2, 1, 3, 2, 4, 5]. 2 está presente en el índice 2.
Consulta 4: mueva 1 de [2, 1, 3, 4, 5] al comienzo de la array para que la array se vea como [1, 2, 3, 4, 5]. 1 está presente en el índice 1.
Entrada:Q[] = {4, 1, 2, 2}, M = 4
Salida: 3, 1, 2, 0
Enfoque ingenuo: el enfoque ingenuo es usar una tabla hash para buscar el elemento y hacer cambios linealmente mediante la realización de intercambios. La complejidad del tiempo será de naturaleza cuadrática para este enfoque.
A continuación se muestra la implementación ingenua del enfoque anterior:
C++
// C++ program to search the element
// in an array for every query and
// move the searched element to
// the front after every query
#include <bits/stdc++.h>
using namespace std;
// Function to find the indices
vector<int> processQueries(int Q[], int m, int n)
{
int a[m + 1], pos[m + 1];
for (int i = 1; i <= m; i++) {
a[i - 1] = i;
pos[i] = i - 1;
}
vector<int> ans;
// iterate in the query array
for (int i = 0; i < n; i++) {
int q = Q[i];
// store current element
int p = pos[q];
ans.push_back(p);
for (int i = p; i > 0; i--) {
// swap positions of the element
swap(a[i], a[i - 1]);
pos[a[i]] = i;
}
pos[a[0]] = 0;
}
// return the result
return ans;
}
// Driver code
int main()
{
// initialise array
int Q[] = { 3, 1, 2, 1 };
int n = sizeof(Q) / sizeof(Q[0]);
int m = 5;
vector<int> ans;
// Function call
ans = processQueries(Q, m, n);
// Print answers to queries
for (int i = 0; i < ans.size(); i++)
cout << ans[i] << " ";
return 0;
}
Java
// Java program to search the element
// in an array for every query and
// move the searched element to
// the front after every query
import java.util.*;
class GFG{
// Function to find the indices
static Vector<Integer> processQueries(int Q[], int m, int n)
{
int []a = new int[m + 1];
int []pos = new int[m + 1];
for (int i = 1; i <= m; i++) {
a[i - 1] = i;
pos[i] = i - 1;
}
Vector<Integer> ans = new Vector<Integer>();
// iterate in the query array
for (int i = 0; i < n; i++) {
int q = Q[i];
// store current element
int p = pos[q];
ans.add(p);
for (int j = p; j > 0; j--) {
// swap positions of the element
a[j] = a[j] + a[j - 1];
a[j - 1] = a[j] - a[j - 1];
a[j] = a[j] - a[j - 1];
pos[a[j]] = j;
}
pos[a[0]] = 0;
}
// return the result
return ans;
}
// Driver code
public static void main(String[] args)
{
// initialise array
int Q[] = { 3, 1, 2, 1 };
int n = Q.length;
int m = 5;
Vector<Integer> ans = new Vector<Integer>();
// Function call
ans = processQueries(Q, m, n);
// Print answers to queries
for (int i = 0; i < ans.size(); i++)
System.out.print(ans.get(i)+ " ");
}
}
// This code is contributed by sapnasingh4991
Python3
# Python3 program to search the element # in an array for every query and # move the searched element to # the front after every query # Function to find the indices def processQueries(Q, m, n) : a = [0]*(m + 1); pos = [0]*(m + 1); for i in range(1, m + 1) : a[i - 1] = i; pos[i] = i - 1; ans = []; # iterate in the query array for i in range(n) : q = Q[i]; # store current element p = pos[q]; ans.append(p); for i in range(p,0,-1) : # swap positions of the element a[i], a[i - 1] = a[i - 1],a[i]; pos[a[i]] = i; pos[a[0]] = 0; # return the result return ans; # Driver code if __name__ == "__main__" : # initialise array Q = [ 3, 1, 2, 1 ]; n = len(Q); m = 5; ans = []; # Function call ans = processQueries(Q, m, n); # Print answers to queries for i in range(len(ans)) : print(ans[i],end=" "); # This code is contributed by Yash_R
C#
// C# program to search the element
// in an array for every query and
// move the searched element to
// the front after every query
using System;
using System.Collections.Generic;
public class GFG{
// Function to find the indices
static List<int> processQueries(int []Q, int m, int n)
{
int []a = new int[m + 1];
int []pos = new int[m + 1];
for(int i = 1; i <= m; i++)
{
a[i - 1] = i;
pos[i] = i - 1;
}
List<int> ans = new List<int>();
// Iterate in the query array
for(int i = 0; i < n; i++)
{
int q = Q[i];
// Store current element
int p = pos[q];
ans.Add(p);
for(int j = p; j > 0; j--)
{
// Swap positions of the element
a[j] = a[j] + a[j - 1];
a[j - 1] = a[j] - a[j - 1];
a[j] = a[j] - a[j - 1];
pos[a[j]] = j;
}
pos[a[0]] = 0;
}
// Return the result
return ans;
}
// Driver code
public static void Main(String[] args)
{
// Initialise array
int []Q = { 3, 1, 2, 1 };
int n = Q.Length;
int m = 5;
List<int> ans = new List<int>();
// Function call
ans = processQueries(Q, m, n);
// Print answers to queries
for(int i = 0; i < ans.Count; i++)
Console.Write(ans[i] + " ");
}
}
// This code is contributed by sapnasingh4991
Javascript
<script>
// JavaScript program to search the element
// in an array for every query and
// move the searched element to
// the front after every query
// Function to find the indices
function processQueries(Q,m,n)
{
let a = new Array(m + 1);
let pos = new Array(m + 1);
for (let i = 1; i <= m; i++) {
a[i - 1] = i;
pos[i] = i - 1;
}
let ans = [];
// iterate in the query array
for (let i = 0; i < n; i++) {
let q = Q[i];
// store current element
let p = pos[q];
ans.push(p);
for (let j = p; j > 0; j--) {
// swap positions of the element
a[j] = a[j] + a[j - 1];
a[j - 1] = a[j] - a[j - 1];
a[j] = a[j] - a[j - 1];
pos[a[j]] = j;
}
pos[a[0]] = 0;
}
// return the result
return ans;
}
// Driver code
// initialise array
let Q=[3, 1, 2, 1];
let n = Q.length;
let m = 5;
let ans=[];
// Function call
ans = processQueries(Q, m, n);
// Print answers to queries
for (let i = 0; i < ans.length; i++)
document.write(ans[i]+ " ");
// This code is contributed by rag2127
</script>
Producción:
2 1 2 1
Enfoque eficiente: un método eficiente para resolver el problema anterior es usar Fenwick Tree. Usando las siguientes 3 operaciones, el problema se puede resolver.
- Elemento de empuje en la parte delantera
- Encontrar el índice de un número
- Actualizar los índices del resto de elementos.
Mantenga los elementos ordenados utilizando la estructura de datos establecida y luego siga los puntos mencionados a continuación:
- En lugar de empujar el elemento al frente, es decir, asignar un índice 0 para cada consulta.
- Asignamos -1 para la primera consulta, -2 para la segunda consulta, -3 para la tercera y así sucesivamente hasta -m.
- Al hacerlo, el rango de actualizaciones del índice a [-m, m]
- Realice un desplazamiento a la derecha para todos los valores [-m, m] por un valor de m, por lo que nuestro nuevo rango es [0, 2m]
- Inicialice un árbol Fenwick de tamaño 2m y establezca todos los valores desde [1…m], es decir, [m..2m]
- Para cada consulta, encuentre su posición encontrando el número de elementos establecidos menor que la consulta dada, una vez hecho, establezca su posición en 0 en el árbol de Fenwick.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to search the element
// in an array for every query and
// move the searched element to
// the front after every query
#include <bits/stdc++.h>
using namespace std;
// Function to update the fenwick tree
void update(vector<int>& tree, int i, int val)
{
// update the next element
while (i < tree.size()) {
tree[i] += val;
// move to the next
i += (i & (-i));
}
}
// Function to get the
// sum from the fenwick tree
int getSum(vector<int>& tree, int i)
{
int s = 0;
// keep adding till we have not
// reached the root of the tree
while (i > 0) {
s += tree[i];
// move to the parent
i -= (i & (-i));
}
return s;
}
// function to process the queries
vector<int> processQueries(vector<int>& queries, int m)
{
vector<int> res, tree((2 * m) + 1, 0);
// Hash-table
unordered_map<int, int> hmap;
// Iterate and increase the frequency
// count in the fenwick tree
for (int i = 1; i <= m; ++i) {
hmap[i] = i + m;
update(tree, i + m, 1);
}
// Traverse for all queries
for (int querie : queries) {
// Get the sum from the fenwick tree
res.push_back(getSum(tree, hmap[querie]) - 1);
// remove it from the fenwick tree
update(tree, hmap[querie], -1);
// Add it back at the first index
update(tree, m, 1);
hmap[querie] = m;
m--;
}
// return the final result
return res;
}
// Driver code
int main()
{
// initialise the Queries
vector<int> Queries = { 4, 1, 2, 2 };
// initialise M
int m = 4;
vector<int> ans;
ans = processQueries(Queries, m);
for (int i = 0; i < ans.size(); i++)
cout << ans[i] << " ";
return 0;
}
Java
// Java program to search the element
// in an array for every query and
// move the searched element to
// the front after every query
import java.util.*;
class GFG{
// Function to update the fenwick tree
static void update(int []tree, int i, int val)
{
// update the next element
while (i < tree.length)
{
tree[i] += val;
// move to the next
i += (i & (-i));
}
}
// Function to get the
// sum from the fenwick tree
static int getSum(int []tree, int i)
{
int s = 0;
// keep adding till we have not
// reached the root of the tree
while (i > 0)
{
s += tree[i];
// move to the parent
i -= (i & (-i));
}
return s;
}
// function to process the queries
static Vector<Integer> processQueries(int []queries,
int m)
{
Vector<Integer>res = new Vector<>();
int []tree = new int[(2 * m) + 1];
// Hash-table
HashMap<Integer,Integer> hmap = new HashMap<>();
// Iterate and increase the frequency
// count in the fenwick tree
for (int i = 1; i <= m; ++i)
{
hmap.put(i, i+m);
update(tree, i + m, 1);
}
// Traverse for all queries
for (int querie : queries)
{
// Get the sum from the fenwick tree
res.add(getSum(tree, hmap.get(querie) - 1));
// remove it from the fenwick tree
update(tree, hmap.get(querie), -1);
// Add it back at the first index
update(tree, m, 1);
hmap.put(querie, m);
m--;
}
// return the final result
return res;
}
// Driver code
public static void main(String[] args)
{
// initialise the Queries
int []Queries = { 4, 1, 2, 2 };
// initialise M
int m = 4;
Vector<Integer> ans;
ans = processQueries(Queries, m);
System.out.print(ans);
}
}
// This code is contributed by Rohit_ranjan
Python3
# Python3 program to search the element
# in an array for every query and
# move the searched element to
# the front after every query
# Function to update the fenwick tree
def update(tree, i, val):
# Update the next element
while (i < len(tree)):
tree[i] += val
# Move to the next
i += (i & (-i))
# Function to get the
# sum from the fenwick tree
def getSum(tree, i):
s = 0
# Keep adding till we have not
# reached the root of the tree
while (i > 0):
s += tree[i]
# Move to the parent
i -= (i & (-i))
return s
# Function to process the queries
def processQueries(queries, m):
res = []
tree = [0] * (2 * m + 1)
# Hash-table
hmap = {}
# Iterate and increase the frequency
# count in the fenwick tree
for i in range(1, m + 1):
hmap[i] = i + m
update(tree, i + m, 1)
# Traverse for all queries
for querie in queries:
# Get the sum from the fenwick tree
res.append(getSum(tree, hmap[querie]) - 1)
# Remove it from the fenwick tree
update(tree, hmap[querie], -1)
# Add it back at the first index
update(tree, m, 1)
hmap[querie] = m
m -= 1
# Return the final result
return res
# Driver code
if __name__ == "__main__":
# Initialise the Queries
Queries = [ 4, 1, 2, 2 ]
# Initialise M
m = 4
ans = processQueries(Queries, m)
for i in range(len(ans)):
print(ans[i], end = " ")
# This code is contributed by chitranayal
C#
// C# program to search the element
// in an array for every query and
// move the searched element to
// the front after every query
using System;
using System.Collections.Generic;
class GFG{
// Function to update the fenwick tree
static void update(int []tree,
int i, int val)
{
// update the next element
while (i < tree.Length)
{
tree[i] += val;
// move to the next
i += (i & (-i));
}
}
// Function to get the
// sum from the fenwick tree
static int getSum(int []tree, int i)
{
int s = 0;
// keep adding till we have not
// reached the root of the tree
while (i > 0)
{
s += tree[i];
// move to the parent
i -= (i & (-i));
}
return s;
}
// function to process the queries
static List<int> processQueries(int []queries,
int m)
{
List<int>res = new List<int>();
int []tree = new int[(2 * m) + 1];
// Hash-table
Dictionary<int,
int> hmap = new Dictionary<int,
int>();
// Iterate and increase the frequency
// count in the fenwick tree
for (int i = 1; i <= m; ++i)
{
hmap.Add(i, i+m);
update(tree, i + m, 1);
}
// Traverse for all queries
foreach (int querie in queries)
{
// Get the sum from the fenwick tree
res.Add(getSum(tree, hmap[querie] - 1));
// remove it from the fenwick tree
update(tree, hmap[querie], -1);
// Add it back at the first index
update(tree, m, 1);
if(hmap.ContainsKey(querie))
hmap[querie] = m;
else
hmap.Add(querie, m);
m--;
}
// return the readonly result
return res;
}
// Driver code
public static void Main(String[] args)
{
// initialise the Queries
int []Queries = {4, 1, 2, 2};
// initialise M
int m = 4;
List<int> ans;
ans = processQueries(Queries, m);
foreach (int i in ans)
Console.Write(i + " ");
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// Javascript program to search the element
// in an array for every query and
// move the searched element to
// the front after every query
// Function to update the fenwick tree
function update(tree,i,val)
{
// update the next element
while (i < tree.length)
{
tree[i] += val;
// move to the next
i += (i & (-i));
}
}
// Function to get the
// sum from the fenwick tree
function getSum(tree,i)
{
let s = 0;
// keep adding till we have not
// reached the root of the tree
while (i > 0)
{
s += tree[i];
// move to the parent
i -= (i & (-i));
}
return s;
}
// function to process the queries
function processQueries(queries,m)
{
let res = [];
let tree = new Array((2 * m) + 1);
for(let i=0;i<tree.length;i++)
{
tree[i]=0;
}
// Hash-table
let hmap = new Map();
// Iterate and increase the frequency
// count in the fenwick tree
for (let i = 1; i <= m; ++i)
{
hmap.set(i, i+m);
update(tree, i + m, 1);
}
// Traverse for all queries
for (let querie=0;querie< queries.length;querie++)
{
// Get the sum from the fenwick tree
res.push(getSum(tree, hmap.get(queries[querie]) - 1));
// remove it from the fenwick tree
update(tree, hmap.get(queries[querie]), -1);
// Add it back at the first index
update(tree, m, 1);
hmap.set(queries[querie], m);
m--;
}
// return the final result
return res;
}
// Driver code
let Queries=[4, 1, 2, 2];
// initialise M
let m = 4;
let ans;
ans = processQueries(Queries, m);
document.write(ans.join(" "));
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
3 1 2 0
Complejidad de tiempo: O(nlogn)
Complejidad de espacio: O(2n)