Consultas para buscar un elemento en una array y moverlo al frente después de cada consulta

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.  

  1. Elemento de empuje en la parte delantera
  2. Encontrar el índice de un número
  3. 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)

Publicación traducida automáticamente

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