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>
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>
3 1 2 0
Complejidad de tiempo: O(nlogn)
Complejidad de espacio: O(2n)