Dada una array arr[] de tamaño N y una array Q[] que consta de M enteros, cada uno de los cuales representa una consulta, la tarea de cada consulta Q[i] es encontrar el índice más pequeño de un elemento de la array cuyo valor es mayor que o igual a Q[i] . Si no existe tal índice, imprima -1 .
Ejemplos:
Entrada: arr[] = { 1, 9 }, Q[] = { 7, 10, 0 }
Salida: 1 -1 0
Explicación:
El índice más pequeño de arr[] cuyo valor es mayor que Q[0] es 1.
No existe tal índice en arr[] cuyo valor sea mayor que Q[1].
El índice más pequeño de arr[] cuyo valor es mayor que Q[2] es 0.
Por lo tanto, la salida requerida es 1 -1 0.Entrada: arr[] = {2, 3, 4}, Q[] = {2, 3, 4}
Salida: 0 1 2
Enfoque: el problema se puede resolver utilizando la técnica de búsqueda binaria y suma de prefijos . Siga los pasos a continuación para resolver el problema:
- Inicialice una array , digamos storeArrIdx[] , de la forma {primero, segundo} para almacenar los elementos de la array junto con el índice.
- Ordene la array storeArridx[] en orden creciente de los elementos de la array .
- Ordene la array arr[] en orden creciente .
- Inicialice una array, digamos minIdx[] , de modo que minIdx[i] almacene el índice más pequeño de un elemento de array cuyo valor sea mayor o igual que arr[i] .
- Recorra la array storeArrIdx[] al revés usando la variable i . Para cada i -ésimo índice, actualice minIdx[i] = min(minIdx[i + 1], storeArrIdx[i].second) .
- Recorra la array Q[] usando la variable i . Para cada i -ésima consulta, encuentre el índice del límite inferior de Q[i] en arr[] y verifique si el índice obtenido es menor que N o no. Si se encuentra que es cierto, imprima minIdx[i] .
- De lo contrario, imprima -1 .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the smallest index
// of an array element whose value is
// less than or equal to Q[i]
void minimumIndex(vector<int>& arr,
vector<int>& Q)
{
// Stores size of array
int N = arr.size();
// Stores count of queries
int M = Q.size();
// Store array elements along
// with the index
vector<pair<int, int> > storeArrIdx;
// Store smallest index of an array
// element whose value is greater
// than or equal to i
vector<int> minIdx(N);
// Traverse the array
for (int i = 0; i < N; ++i) {
// Insert {arr[i], i} into
// storeArrIdx[]
storeArrIdx.push_back({ arr[i], i });
}
// Sort the array
sort(arr.begin(), arr.end());
// Sort the storeArrIdx
sort(storeArrIdx.begin(),
storeArrIdx.end());
// Stores index of arr[N - 1] in
// sorted order
minIdx[N - 1]
= storeArrIdx[N - 1].second;
// Traverse the array storeArrIdx[]
for (int i = N - 2; i >= 0; i--) {
// Update minIdx[i]
minIdx[i] = min(minIdx[i + 1],
storeArrIdx[i].second);
}
// Traverse the array Q[]
for (int i = 0; i < M; i++) {
// Store the index of
// lower_bound of Q[i]
int pos
= lower_bound(arr.begin(),
arr.end(), Q[i])
- arr.begin();
// If no index found whose value
// greater than or equal to arr[i]
if (pos == N) {
cout << -1 << " ";
continue;
}
// Print smallest index whose value
// greater than or equal to Q[i]
cout << minIdx[pos] << " ";
}
}
// Driver Code
int main()
{
vector<int> arr = { 1, 9 };
vector<int> Q = { 7, 10, 0 };
minimumIndex(arr, Q);
return 0;
}
Java
// Java program for above approach
import java.util.*;
import java.lang.*;
class pair
{
int element,index;
pair(int element, int index)
{
this.element = element;
this.index = index;
}
}
class GFG
{
// Function to find the smallest index
// of an array element whose value is
// less than or equal to Q[i]
static void minimumIndex(int[] arr,
int[] Q)
{
// Stores size of array
int N = arr.length;
// Stores count of queries
int M = Q.length;
// Store array elements along
// with the index
ArrayList<pair> storeArrIdx = new ArrayList<>();
// Store smallest index of an array
// element whose value is greater
// than or equal to i
int[] minIdx = new int[N];
// Traverse the array
for (int i = 0; i < N; ++i)
{
// Insert {arr[i], i} into
// storeArrIdx[]
storeArrIdx.add(new pair(arr[i], i));
}
// Sort the array
Arrays.sort(arr);
// Sort the storeArrIdx
Collections.sort(storeArrIdx, (a, b)->a.element-b.element);
// Stores index of arr[N - 1] in
// sorted order
minIdx[N - 1]
= storeArrIdx.get(N - 1).index;
// Traverse the array storeArrIdx[]
for (int i = N - 2; i >= 0; i--) {
// Update minIdx[i]
minIdx[i] =Math.min(minIdx[i + 1],
storeArrIdx.get(i).index);
}
// Traverse the array Q[]
for (int i = 0; i < M; i++) {
// Store the index of
// lower_bound of Q[i]
int pos
= lower_bound(arr, Q[i]);
// If no index found whose value
// greater than or equal to arr[i]
if (pos == N) {
System.out.print("-1"+" ");
continue;
}
// Print smallest index whose value
// greater than or equal to Q[i]
System.out.print(minIdx[pos]+" ");
}
}
static int lower_bound(int[] arr,int element)
{
for(int i = 0; i < arr.length; i++)
if(element <= arr[i])
return i;
return arr.length;
}
// Driver function
public static void main (String[] args)
{
int[] arr = { 1, 9 };
int[] Q = { 7, 10, 0 };
minimumIndex(arr, Q);
}
}
// This code is contributed by offbeat
Python3
# Python3 program to implement
# the above approachf
from bisect import bisect_left
# Function to find the smallest index
# of an array element whose value is
# less than or equal to Q[i]
def minimumIndex(arr, Q):
# Stores size of array
N = len(arr)
# Stores count of queries
M = len(Q)
# Store array elements along
# with the index
storeArrIdx = []
# Store smallest index of an array
# element whose value is greater
# than or equal to i
minIdx = [0]*(N)
# Traverse the array
for i in range(N):
# Insert {arr[i], i} into
# storeArrIdx[]
storeArrIdx.append([arr[i], i])
# Sort the array
arr = sorted(arr)
# Sort the storeArrIdx
storeArrIdx = sorted(storeArrIdx)
# Stores index of arr[N - 1] in
# sorted order
minIdx[N - 1] = storeArrIdx[N - 1][1]
# Traverse the array storeArrIdx[]
for i in range(N - 2, -1, -1):
# Update minIdx[i]
minIdx[i] = min(minIdx[i + 1], storeArrIdx[i][1])
# Traverse the array Q[]
for i in range(M):
# Store the index of
# lower_bound of Q[i]
pos = bisect_left(arr, Q[i])
# If no index found whose value
# greater than or equal to arr[i]
if (pos == N):
print(-1, end = " ")
continue
# Print smallest index whose value
# greater than or equal to Q[i]
print(minIdx[pos], end = " ")
# Driver Code
if __name__ == '__main__':
arr = [1, 9]
Q = [7, 10, 0]
minimumIndex(arr, Q)
# This code is contributed by mohit kumar 29
Javascript
<script>
// JavaScript program for above approach
class pair
{
constructor(element,index)
{
this.element = element;
this.index = index;
}
}
// Function to find the smallest index
// of an array element whose value is
// less than or equal to Q[i]
function minimumIndex(arr,Q)
{
// Stores size of array
let N = arr.length;
// Stores count of queries
let M = Q.length;
// Store array elements along
// with the index
let storeArrIdx = [];
// Store smallest index of an array
// element whose value is greater
// than or equal to i
let minIdx = new Array(N);
for(let i=0;i<N;i++)
{
minIdx[i]=0;
}
// Traverse the array
for (let i = 0; i < N; ++i)
{
// Insert {arr[i], i} into
// storeArrIdx[]
storeArrIdx.push([arr[i], i]);
}
// Sort the array
(arr).sort(function(a,b){return a-b;});
// Sort the storeArrIdx
storeArrIdx.sort(function(a, b){ return a[0]-b[0]});
// Stores index of arr[N - 1] in
// sorted order
minIdx[N - 1]
= storeArrIdx[N - 1][1];
// Traverse the array storeArrIdx[]
for (let i = N - 2; i >= 0; i--) {
// Update minIdx[i]
minIdx[i] =Math.min(minIdx[i + 1],
storeArrIdx[i][1]);
}
// Traverse the array Q[]
for (let i = 0; i < M; i++) {
// Store the index of
// lower_bound of Q[i]
let pos
= lower_bound(arr, Q[i]);
// If no index found whose value
// greater than or equal to arr[i]
if (pos == N) {
document.write("-1"+" ");
continue;
}
// Print smallest index whose value
// greater than or equal to Q[i]
document.write(minIdx[pos]+" ");
}
}
function lower_bound(arr,element)
{
for(let i = 0; i < arr.length; i++)
if(element <= arr[i])
return i;
return arr.length;
}
// Driver function
let arr=[1, 9];
let Q=[7, 10, 0 ];
minimumIndex(arr, Q);
// This code is contributed by patel2127
</script>
Producción:
1 -1 0
Complejidad de tiempo: O(N * log(N))
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA