Consultas para devolver la diferencia absoluta entre el L-ésimo número más pequeño y el R-ésimo número más pequeño

Dada una array arr[] de N elementos únicos y Q consultas. Cada consulta consta de dos números enteros L y R . La tarea es imprimir la diferencia absoluta entre los índices del L th más pequeño y el R th más pequeño elemento. 

Ejemplos: 

Entrada: arr[] = {1, 5, 4, 2, 8, 6, 7}, 
que[] = {{2, 5}, {1, 3}, {1, 5}, {3, 6} } 
Salida: 




Para la primera consulta, el segundo número más pequeño es 2, que está en el índice 3 
y el quinto número más pequeño es 6, que está en el índice 5. Por lo tanto, la 
diferencia absoluta entre ambos índices es 2.

Entrada: arr[] = {1, 2, 3, 4}, 
que[] = {{1, 1}, {2, 3}} 
Salida: 

Enfoque: Se pueden seguir los siguientes pasos para resolver el problema anterior.  

  • Almacene los elementos y sus índices en una array de pares.
  • Ordene la array según el primer elemento.
  • Para cada consulta, la respuesta será abs(arr[l – 1].segundo – arr[r – 1].segundo)

A continuación se muestra la implementación del enfoque anterior:  

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the result
// for a particular query
int answerQuery(pair<int, int> arr[], int l, int r)
{
    // Get the difference between the indices of
    // L-th and the R-th smallest element
    int answer = abs(arr[l - 1].second - arr[r - 1].second);
 
    // Return the answer
    return answer;
}
 
// Function that performs all the queries
void solveQueries(int a[], int n, int q[][2], int m)
{
 
    // Store the array numbers
    // and their indices
    pair<int, int> arr[n];
    for (int i = 0; i < n; i++) {
        arr[i].first = a[i];
        arr[i].second = i;
    }
 
    // Sort the array elements
    sort(arr, arr + n);
 
    // Answer all the queries
    for (int i = 0; i < m; i++)
        cout << answerQuery(arr, q[i][0], q[i][1]) << endl;
}
 
// Driver code
int main()
{
    int a[] = { 1, 5, 4, 2, 8, 6, 7 };
    int n = sizeof(a) / sizeof(a[0]);
    int q[][2] = { { 2, 5 }, { 1, 3 }, { 1, 5 }, { 3, 6 } };
    int m = sizeof(q) / sizeof(q[0]);
    solveQueries(a, n, q, m);
 
    return 0;
}

Java

// Java implementation of the approach
import java.util.*;
import java.util.Comparator;
 
class GFG
{
     
// pair class
static class pair
{
    int first,second;
    pair(int f, int s)
    {
        first = f;
        second = s;
    }
}
 
// Function to return the result
// for a particular query
static int answerQuery(pair arr[], int l, int r)
{
    // Get the difference between the indices of
    // L-th and the R-th smallest element
    int answer = Math.abs(arr[l - 1].second -
                        arr[r - 1].second);
 
    // Return the answer
    return answer;
}
 
// Function that performs all the queries
static void solveQueries(int a[], int n,
                        int q[][], int m)
{
 
    // Store the array numbers
    // and their indices
    pair arr[] = new pair[n];
    for (int i = 0; i < n; i++)
    {
        arr[i] = new pair(0, 0);
        arr[i].first = a[i];
        arr[i].second = i;
    }
        // Sort pair
        Comparator<pair> comp = new Comparator<pair>()
        {
             
            public int compare(pair e1, pair e2)
            {
                if(e1.first < e2.first)
                {
                    return -1;
                }
                else if (e1.first > e2.first)
                {
                    return 1;
                }
                else
                {
                    return 0;
                }
            }
        };
         
    // Sort the array elements
    Arrays.sort(arr,comp);
 
    // Answer all the queries
    for (int i = 0; i < m; i++)
        System.out.println( answerQuery(arr, q[i][0], q[i][1]));
}
 
// Driver code
public static void main(String args[])
{
    int a[] = { 1, 5, 4, 2, 8, 6, 7 };
    int n = a.length;
    int q[][] = { { 2, 5 }, { 1, 3 }, { 1, 5 }, { 3, 6 } };
    int m = q.length;
    solveQueries(a, n, q, m);
}
}
 
// This code is contributed by Arnab Kundu

Python3

# Python 3 implementation of the approach
 
# Function to return the result
# for a particular query
def answerQuery(arr, l, r):
     
    # Get the difference between the indices
    # of L-th and the R-th smallest element
    answer = abs(arr[l - 1][1] -
                 arr[r - 1][1])
 
    # Return the answer
    return answer
 
# Function that performs all the queries
def solveQueries(a, n, q, m):
     
    # Store the array numbers
    # and their indices
    arr = [[0 for i in range(n)]
              for j in range(n)]
    for i in range(n):
        arr[i][0] = a[i]
        arr[i][1] = i
 
    # Sort the array elements
    arr.sort(reverse = False)
 
    # Answer all the queries
    for i in range(m):
        print(answerQuery(arr, q[i][0],
                               q[i][1]))
 
# Driver code
if __name__ == '__main__':
    a = [1, 5, 4, 2, 8, 6, 7]
    n = len(a)
    q = [[2, 5], [1, 3],
         [1, 5], [3, 6]]
    m = len(q)
    solveQueries(a, n, q, m)
 
# This code is contributed by
# Surendra_Gangwar

Javascript

<script>
 
// JavaScript implementation of the approach
 
 
// Function to return the result
// for a particular query
function answerQuery(arr, l, r)
{
    // Get the difference between the indices of
    // L-th and the R-th smallest element
    let answer = Math.abs(arr[l - 1][1] - arr[r - 1][1]);
 
    // Return the answer
    return answer;
}
 
// Function that performs all the queries
function solveQueries(a, n, q, m)
{
 
    // Store the array numbers
    // and their indices
    let arr = new Array(n);
 
     
    for(let i = 0; i < n; i++){
        arr[i] = new Array(n).fill(0)
    }
 
    for (let i = 0; i < n; i++) {
        arr[i][0] = a[i];
        arr[i][1] = i;
    }
 
    // Sort the array elements
    arr.sort((a, b) => a[0] - b[0]);
 
    // Answer all the queries
    for (let i = 0; i < m; i++)
        document.write(answerQuery(arr, q[i][0], q[i][1]) +
        "<br>");
}
 
// Driver code
 
    let a = [ 1, 5, 4, 2, 8, 6, 7 ];
    let n = a.length;
    let q = [ [ 2, 5 ], [ 1, 3 ], [ 1, 5 ], [ 3, 6 ] ];
    let m = q.length;
    solveQueries(a, n, q, m);
 
// This code is contributed by _saurabh_jaiswal
 
</script>
Producción: 

2
2
5
4

 

Complejidad de tiempo: O(N*logN), ya que estamos usando una función de ordenación incorporada para ordenar una array de tamaño N. Donde N es el número de elementos en la array.

Espacio auxiliar: O(N), ya que estamos usando espacio extra para el arreglo arr de tamaño N. Donde N es el número de elementos en el arreglo.

Publicación traducida automáticamente

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