Dada una array que contiene N elementos distintos. Hay M consultas, cada una de las cuales contiene un número entero X y solicita el índice de X en la array. Para cada consulta, la tarea es realizar una búsqueda lineal X de izquierda a derecha y contar el número de comparaciones necesarias para encontrar X y hacer lo mismo de derecha a izquierda. Al final, imprima el número total de comparaciones en ambas direcciones entre todas las consultas.
Ejemplos:
Entrada: arr[] = {1, 2}, q[] = {1, 2}
Salida: 3, 3
Para indexación basada en
1 Para la primera consulta: el número de comparaciones de izquierda a derecha es 1 y de derecha a izquierda es 2
Para la segunda consulta: el número de comparaciones de izquierda a derecha es 2 y de derecha a izquierda es 1
Entrada: arr[] = {-1, 2, 4, 5, 1}, q[] = {-1, 4, 2}
Salida: 3, 7
Enfoque: Encuentre el índice en el que X está presente en la array, digamos i (indexación basada en 1), el número de comparaciones de izquierda a derecha sería i y el número de comparaciones de derecha a izquierda sería (n – i + 1 ) . Todo lo que tenemos que hacer es encontrar el índice rápidamente. Se puede hacer usando un mapa en el que la clave es el valor del elemento y el valor es el índice.
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 count of comparisons from left to right
// and right to left in linear search among m queries
pair<int, int> countCamparisions(int n, int arr[], int m, int qry[])
{
int i;
unordered_map<int, int> index;
for (i = 1; i <= n; i++) {
// arr[i] occurs at i
index[arr[i]] = i;
}
// Count of comparisons for left to right and right to left
int ltr = 0, rtl = 0;
for (i = 1; i <= m; i++) {
int x = qry[i];
ltr += index[x];
rtl += n - index[x] + 1;
}
return make_pair(ltr, rtl);
}
// Driver Code
int main()
{
// -1 will be ignored as it is 1-based indexing
int arr[] = { -1, 2, 4, 5, 1 };
int n = (sizeof(arr) / sizeof(arr[0])) - 1;
int q[] = { -1, 4, 2 };
int m = (sizeof(q) / sizeof(q[0])) - 1;
pair<int, int> res = countCamparisions(n, arr, m, q);
cout << res.first << " " << res.second;
}
Java
// Java implementation of the approach
import java.util.HashMap;
import java.util.Map;
class GFG
{
// Function to return the count of
// comparisons from left to right
// and right to left in linear
// search among m queries
static Pair<Integer, Integer> countCamparisions(int n,
int arr[], int m, int qry[])
{
int i;
HashMap<Integer,Integer> index = new HashMap<>();
for (i = 1; i <= n; i++)
{
// arr[i] occurs at i
index.put(arr[i], i);
}
// Count of comparisons for left
// to right and right to left
int ltr = 0, rtl = 0;
for (i = 1; i <= m; i++)
{
int x = qry[i];
ltr += index.get(x);
rtl += n - index.get(x) + 1;
}
Pair<Integer, Integer> ans = new Pair<>(ltr, rtl);
return ans;
}
// Driver Code
public static void main(String []args)
{
// -1 will be ignored as it is 1-based indexing
int arr[] = { -1, 2, 4, 5, 1 };
int n = arr.length - 1;
int q[] = { -1, 4, 2 };
int m = q.length - 1;
Pair<Integer, Integer> res = countCamparisions(n, arr, m, q);
System.out.println(res.first + " " + res.second);
}
}
class Pair<A, B>
{
A first;
B second;
public Pair(A first, B second)
{
this.first = first;
this.second = second;
}
}
// This code is contributed by Rituraj Jain
Python3
# Python 3 implementation of the
# above approach
# Function to return the count of
# comparisons from left to right
# and right to left in linear search
# among m queries
def countCamparisions(n, arr, m, qry) :
index = {}
for i in range(1, n + 1) :
# arr[i] occurs at i
index[arr[i]] = i
# Count of comparisons for left to
# right and right to left
ltr, rtl = 0, 0
for i in range(1, m + 1) :
x = qry[i]
ltr += index[x]
rtl += n - index[x] + 1
return (ltr, rtl)
# Driver Code
if __name__ == "__main__" :
# -1 will be ignored as it
# is 1-based indexing
arr = [ -1, 2, 4, 5, 1 ]
n = len(arr) - 1
q = [ -1, 4, 2 ]
m = len(q) - 1
res = countCamparisions(n, arr, m, q)
print(res[0], res[1])
# This code is contributed by Ryuga
C#
// C# implementation of the approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to return the count of
// comparisons from left to right
// and right to left in linear
// search among m queries
static Pair<int,
int> countCamparisions(int n, int []arr,
int m, int []qry)
{
int i;
Dictionary<int,
int> index = new Dictionary<int,
int>();
for (i = 1; i <= n; i++)
{
// arr[i] occurs at i
index.Add(arr[i], i);
}
// Count of comparisons for left
// to right and right to left
int ltr = 0, rtl = 0;
for (i = 1; i <= m; i++)
{
int x = qry[i];
ltr += index[x];
rtl += n - index[x] + 1;
}
Pair<int,
int> ans = new Pair<int,
int>(ltr, rtl);
return ans;
}
// Driver Code
public static void Main(String []args)
{
// -1 will be ignored as
// it is 1-based indexing
int []arr = { -1, 2, 4, 5, 1 };
int n = arr.Length - 1;
int []q = { -1, 4, 2 };
int m = q.Length - 1;
Pair<int, int> res = countCamparisions(n, arr, m, q);
Console.WriteLine(res.first + " " + res.second);
}
}
class Pair<A, B>
{
public A first;
public B second;
public Pair(A first, B second)
{
this.first = first;
this.second = second;
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript implementation of the approach
// Function to return the count of comparisons from left to right
// and right to left in linear search among m queries
function countCamparisions(n, arr, m, qry)
{
var i;
var index = new Map();
for (i = 1; i <= n; i++) {
// arr[i] occurs at i
index.set(arr[i], i);
}
// Count of comparisons for left to right and right to left
var ltr = 0, rtl = 0;
for (i = 1; i <= m; i++) {
var x = qry[i];
ltr += index.get(x);
rtl += n - index.get(x) + 1;
}
return [ltr, rtl];
}
// Driver Code
// -1 will be ignored as it is 1-based indexing
var arr = [-1, 2, 4, 5, 1];
var n = arr.length - 1;
var q = [-1, 4, 2];
var m = q.length - 1;
var res = countCamparisions(n, arr, m, q);
document.write( res[0] + " " + res[1]);
// This code is contributed by famously.
</script>
3 7
Complejidad temporal: O(N + M)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por Abdullah Aslam y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA