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:
2
2
5
4
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:
0
1
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.