Dada una array de enteros arr[] de tamaño N y Q consultas de la forma {L, R, X} , la tarea es encontrar el índice más pequeño entre L y R de la array dada tal que arr[i] != X. _ Si no existe tal índice en la array, imprima -1 .
Ejemplos:
Entrada: arr[] = {1, 2, 1, 1, 3, 5}, consulta[][] = {{0, 3, 1}, {1, 5, 2}, {2, 3, 1} }
Salida: 1
2
-1
Explicación:
El primer índice del 0 al 3 que no contiene 1 es 1
El primer índice del 1 al 5 que no contiene 2 es 2
Todos los índices del 2 al 3 contienen 1. Por lo tanto, el la respuesta es -1Entrada: arr[] = { 1, 2, 3, 2, 1, 1, 3, 5}, consulta[][] = { { 1, 4, 2 }, { 4, 5, 1 }, { 2, 3, 1 }, { 4, 6, 1 }}
Salida: 2
-1
2
6
Enfoque ingenuo:
itere sobre el rango [L, R] para cada consulta y verifique si existe algún índice que no contenga X . Si se encuentra dicho índice, imprima ese índice. De lo contrario, imprima -1 .
Complejidad Temporal: O (N * Q)
Espacio Auxiliar: O (1)
Enfoque eficiente:
el enfoque anterior se puede optimizar aún más precomputando y almacenando el índice del siguiente elemento que es diferente del elemento actual, para cada elemento de la array, lo que reduce la complejidad computacional a O(1) para cada consulta.
Siga los pasos a continuación para resolver el problema:
- Cree una array auxiliar nextpos[] para almacenar para cada elemento de la array, el índice del siguiente elemento que es diferente del elemento actual.
- Ahora, para procesar cada consulta, primero verifique si el valor en el índice L no es igual a X. Si es así , entonces la respuesta será L.
- De lo contrario, significa que arr[L] = X . En este caso, necesitamos encontrar el siguiente índice que tenga un valor diferente de arr[L] . Esto se puede obtener de nextpos[L] .
- Si nextpos[L] es menor que igual a R , imprima nexpos[L].
- Si no se cumple ninguna de las condiciones anteriores, la respuesta será -1 .
Ilustración:
arr[] = {1, 2, 1, 1, 3, 5}, consulta[][] = {{0, 3, 1}, {1, 5, 2}, {2, 3, 1}}
Para la array dada arr[], nextpos[] será {1, 2, 4, 4, 5, 6}
Para la primera consulta: L = 0, R = 3, X = 1
arr[0] = 1 = X
nextpos[ 0] = 1( < 3)
Por lo tanto, la respuesta es 1.
Para la segunda consulta: L = 1, R = 5, X = 2
arr[1] = 2( = X)
nextpos[1] = 2( < 5 )
Por lo tanto, la respuesta es 2.
Para la tercera consulta: L = 2, R = 3, X = 1
arr[2] = 1( = X)
nextpos[2] = 4( > R)
Por lo tanto, la respuesta es – 1
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to find the smallest
// index in the array in the range
// [L, R] which does not contain X
#include <bits/stdc++.h>
using namespace std;
// Precompute the index of next
// different element in the array
// for every array element
void precompute(int nextpos[], int arr[],
int N)
{
// Default value
nextpos[N - 1] = N;
for (int i = N - 2; i >= 0; i--) {
// Compute nextpos[i] using
// nextpos[i+1]
if (arr[i] == arr[i + 1])
nextpos[i] = nextpos[i + 1];
else
nextpos[i] = i + 1;
}
}
// Function to return the smallest index
void findIndex(int query[][3], int arr[],
int N, int Q)
{
// nextpos[i] will store the next
// position p where arr[p]!=arr[i]
int nextpos[N];
precompute(nextpos, arr, N);
for (int i = 0; i < Q; i++) {
int l, r, x;
l = query[i][0];
r = query[i][1];
x = query[i][2];
int ans = -1;
// If X is not present at l
if (arr[l] != x)
ans = l;
// Otherwise
else {
// Find the index which
// stores a value different
// from X
int d = nextpos[l];
// If that index is within
// the range
if (d <= r)
ans = d;
}
cout << ans << "\n";
}
}
// Driver Code
int main()
{
int N, Q;
N = 6;
Q = 3;
int arr[] = { 1, 2, 1, 1, 3, 5 };
int query[Q][3] = { { 0, 3, 1 },
{ 1, 5, 2 },
{ 2, 3, 1 } };
findIndex(query, arr, N, Q);
return 0;
}
Java
// Java program to find the smallest
// index in the array in the range
// [L, R] which does not contain X
class GFG{
// Precompute the index of next
// different element in the array
// for every array element
static void precompute(int nextpos[], int arr[],
int N)
{
// Default value
nextpos[N - 1] = N;
for(int i = N - 2; i >= 0; i--)
{
// Compute nextpos[i] using
// nextpos[i+1]
if (arr[i] == arr[i + 1])
nextpos[i] = nextpos[i + 1];
else
nextpos[i] = i + 1;
}
}
// Function to return the smallest index
static void findIndex(int query[][], int arr[],
int N, int Q)
{
// nextpos[i] will store the next
// position p where arr[p]!=arr[i]
int []nextpos = new int[N];
precompute(nextpos, arr, N);
for(int i = 0; i < Q; i++)
{
int l, r, x;
l = query[i][0];
r = query[i][1];
x = query[i][2];
int ans = -1;
// If X is not present at l
if (arr[l] != x)
ans = l;
// Otherwise
else
{
// Find the index which
// stores a value different
// from X
int d = nextpos[l];
// If that index is within
// the range
if (d <= r)
ans = d;
}
System.out.print(ans + "\n");
}
}
// Driver Code
public static void main(String[] args)
{
int N, Q;
N = 6;
Q = 3;
int arr[] = { 1, 2, 1, 1, 3, 5 };
int query[][] = { { 0, 3, 1 },
{ 1, 5, 2 },
{ 2, 3, 1 } };
findIndex(query, arr, N, Q);
}
}
// This code is contributed by Amit Katiyar
Python3
# Python3 program to find the smallest # index in the array in the range # [L, R] which does not contain X # Precompute the index of next # different element in the array # for every array element def precompute(nextpos, arr, N): # Default value nextpos[N - 1] = N for i in range(N - 2, -1, -1): # Compute nextpos[i] using # nextpos[i+1] if arr[i] == arr[i + 1]: nextpos[i] = nextpos[i + 1] else: nextpos[i] = i + 1 # Function to return the smallest index def findIndex(query, arr, N, Q): # nextpos[i] will store the next # position p where arr[p]!=arr[i] nextpos = [0] * N precompute(nextpos, arr, N) for i in range(Q): l = query[i][0] r = query[i][1] x = query[i][2] ans = -1 # If X is not present at l if arr[l] != x: ans = l # Otherwise else: # Find the index which # stores a value different # from X d = nextpos[l] # If that index is within # the range if d <= r: ans = d print(ans) # Driver code N = 6 Q = 3 arr = [ 1, 2, 1, 1, 3, 5 ] query = [ [ 0, 3, 1 ], [ 1, 5, 2 ], [ 2, 3, 1 ] ] findIndex(query, arr, N, Q) # This code is contributed by divyeshrabadiya07
C#
// C# program to find the smallest
// index in the array in the range
// [L, R] which does not contain X
using System;
class GFG{
// Precompute the index of next
// different element in the array
// for every array element
static void precompute(int []nextpos,
int []arr, int N)
{
// Default value
nextpos[N - 1] = N;
for(int i = N - 2; i >= 0; i--)
{
// Compute nextpos[i] using
// nextpos[i+1]
if (arr[i] == arr[i + 1])
nextpos[i] = nextpos[i + 1];
else
nextpos[i] = i + 1;
}
}
// Function to return the smallest index
static void findIndex(int [,]query, int []arr,
int N, int Q)
{
// nextpos[i] will store the next
// position p where arr[p]!=arr[i]
int []nextpos = new int[N];
precompute(nextpos, arr, N);
for(int i = 0; i < Q; i++)
{
int l, r, x;
l = query[i, 0];
r = query[i, 1];
x = query[i, 2];
int ans = -1;
// If X is not present at l
if (arr[l] != x)
ans = l;
// Otherwise
else
{
// Find the index which
// stores a value different
// from X
int d = nextpos[l];
// If that index is within
// the range
if (d <= r)
ans = d;
}
Console.Write(ans + "\n");
}
}
// Driver Code
public static void Main(String[] args)
{
int N, Q;
N = 6;
Q = 3;
int []arr = { 1, 2, 1, 1, 3, 5 };
int [,]query = { { 0, 3, 1 },
{ 1, 5, 2 },
{ 2, 3, 1 } };
findIndex(query, arr, N, Q);
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// Javascript Program to find the smallest
// index in the array in the range
// [L, R] which does not contain X
// Precompute the index of next
// different element in the array
// for every array element
function precompute(nextpos, arr, N)
{
// Default value
nextpos[N - 1] = N;
for (var i = N - 2; i >= 0; i--) {
// Compute nextpos[i] using
// nextpos[i+1]
if (arr[i] == arr[i + 1])
nextpos[i] = nextpos[i + 1];
else
nextpos[i] = i + 1;
}
}
// Function to return the smallest index
function findIndex(query, arr, N, Q)
{
// nextpos[i] will store the next
// position p where arr[p]!=arr[i]
var nextpos = Array(N);
precompute(nextpos, arr, N);
for (var i = 0; i < Q; i++) {
var l, r, x;
l = query[i][0];
r = query[i][1];
x = query[i][2];
var ans = -1;
// If X is not present at l
if (arr[l] != x)
ans = l;
// Otherwise
else {
// Find the index which
// stores a value different
// from X
var d = nextpos[l];
// If that index is within
// the range
if (d <= r)
ans = d;
}
document.write( ans + "<br>");
}
}
// Driver Code
var N, Q;
N = 6;
Q = 3;
var arr = [1, 2, 1, 1, 3, 5];
var query = [ [ 0, 3, 1 ],
[ 1, 5, 2 ],
[ 2, 3, 1 ] ];
findIndex(query, arr, N, Q);
</script>
1 2 -1
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por rohitpal210 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA