Dada una array de N enteros y Q consultas. Cada consulta consta de L y R. La tarea es imprimir el segundo elemento más pequeño en el rango LR. Imprime -1 si no existe el segundo elemento más pequeño.
Ejemplos:
Entrada:
a[] = {1, 2, 2, 4}
Consultas= 2
L = 1, R = 2
L = 0, R = 1
Salida:
-1
2
Enfoque: Procese cada consulta e imprima la segunda más pequeña utilizando el siguiente algoritmo.
- Inicialice tanto el primero como el segundo más pequeño como INT_MAX
- Bucle a través de todos los elementos.
- Si el elemento actual es más pequeño que el primero, actualice primero y segundo.
- De lo contrario, si el elemento actual es más pequeño que el segundo, actualice el segundo
Si el segundo elemento sigue siendo INT_MAX después de recorrer todos los elementos, imprima -1; de lo contrario, imprima el segundo elemento más pequeño.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for
// SP - Second Smallest in Range
#include <bits/stdc++.h>
using namespace std;
// Function to find the second smallest element
// in range L-R of an array
int secondSmallest(int a[], int n, int l, int r)
{
int first = INT_MAX;
int second = INT_MAX;
for (int i = l; i <= r; i++) {
if (a[i] < first) {
second = first;
first = a[i];
}
else if (a[i] < second and a[i] != first) {
second = a[i];
}
}
if (second == INT_MAX)
return -1;
else
return second;
}
// function to perform queries
void performQueries(int a[], int n)
{
// 1-st query
int l = 1;
int r = 2;
cout << secondSmallest(a, n, l, r) << endl;
// 2nd query
l = 0;
r = 1;
cout << secondSmallest(a, n, l, r);
}
// Driver Code
int main()
{
int a[] = { 1, 2, 2, 4 };
int n = sizeof(a) / sizeof(a[0]);
performQueries(a, n);
return 0;
}
Java
// Java program for
// SP - Second Smallest in Range
class GFG
{
// Function to find the
// second smallest element
// in range L-R of an array
static int secondSmallest(int a[], int n,
int l, int r)
{
int first = Integer.MAX_VALUE;
int second = Integer.MAX_VALUE;
for (int i = l; i <= r; i++)
{
if (a[i] < first)
{
second = first;
first = a[i];
}
else if (a[i] < second &&
a[i] != first)
{
second = a[i];
}
}
if (second == Integer.MAX_VALUE)
return -1;
else
return second;
}
// function to perform queries
static void performQueries(int a[], int n)
{
// 1-st query
int l = 1;
int r = 2;
System.out.println(secondSmallest(a, n, l, r));
// 2nd query
l = 0;
r = 1;
System.out.println(secondSmallest(a, n, l, r));
}
// Driver Code
public static void main(String[] args)
{
int a[] = { 1, 2, 2, 4 };
int n = a.length;
performQueries(a, n);
}
}
// This code is contributed
// by ChitraNayal
Python
# Python program for # SP - Second Smallest in Range # Function to find the # second smallest element # in range L-R of an array import sys def secondSmallest(a, n, l, r): first = sys.maxsize second = sys.maxsize for i in range(l, r + 1): if (a[i] < first): second = first first = a[i] elif (a[i] < second and a[i] != first): second = a[i] if (second == sys.maxsize): return -1 else: return second # function to perform queries def performQueries(a, n): # 1-st query l = 1 r = 2 print(secondSmallest(a, n, l, r)) # 2nd query l = 0 r = 1 print(secondSmallest(a, n, l, r)) # Driver Code a = [1, 2, 2, 4 ] n = len(a) performQueries(a, n); # This code is contributed # by Shivi_Aggarwal
C#
// C# program for
// SP - Second Smallest in Range
using System;
class GFG
{
// Function to find the
// second smallest element
// in range L-R of an array
static int secondSmallest(int[] a, int n,
int l, int r)
{
int first = int.MaxValue;
int second = int.MaxValue;
for (int i = l; i <= r; i++)
{
if (a[i] < first)
{
second = first;
first = a[i];
}
else if (a[i] < second &&
a[i] != first)
{
second = a[i];
}
}
if (second == int.MaxValue)
return -1;
else
return second;
}
// function to perform queries
static void performQueries(int[] a, int n)
{
// 1-st query
int l = 1;
int r = 2;
Console.WriteLine(secondSmallest(a, n, l, r));
// 2nd query
l = 0;
r = 1;
Console.WriteLine(secondSmallest(a, n, l, r));
}
// Driver Code
public static void Main()
{
int[] a = { 1, 2, 2, 4 };
int n = a.Length;
performQueries(a, n);
}
}
// This code is contributed
// by ChitraNayal
PHP
<?php
// PHP program for
// SP - Second Smallest in Range
// Function to find the
// second smallest element
// in range L-R of an array
function secondSmallest(&$a, $n, $l, $r)
{
$first = PHP_INT_MAX;
$second = PHP_INT_MAX;
for ($i = $l; $i <= $r; $i++)
{
if ($a[$i] < $first)
{
$second = $first;
$first = $a[$i];
}
else if ($a[$i] < $second and
$a[$i] != $first)
{
$second = $a[$i];
}
}
if ($second == PHP_INT_MAX)
return -1;
else
return $second;
}
// function to perform queries
function performQueries(&$a, $n)
{
// 1-st query
$l = 1;
$r = 2;
echo secondSmallest($a, $n,
$l, $r)."\n";
// 2nd query
$l = 0;
$r = 1;
echo secondSmallest($a, $n,
$l, $r)."\n";
}
// Driver Code
$a = array(1, 2, 2, 4);
$n = sizeof($a);
performQueries($a, $n);
// This code is contributed
// by ChitraNayal
?>
Javascript
<script>
// Javascript program for
// SP - Second Smallest in Range
// Function to find the
// second smallest element
// in range L-R of an array
function secondSmallest(a,n,l,r)
{
let first = Number.MAX_VALUE;
let second = Number.MAX_VALUE;
for (let i = l; i <= r; i++)
{
if (a[i] < first)
{
second = first;
first = a[i];
}
else if (a[i] < second &&
a[i] != first)
{
second = a[i];
}
}
if (second == Number.MAX_VALUE)
return -1;
else
return second;
}
// function to perform queries
function performQueries(a,n)
{
// 1-st query
let l = 1;
let r = 2;
document.write(secondSmallest(a, n, l, r)+"<br>");
// 2nd query
l = 0;
r = 1;
document.write(secondSmallest(a, n, l, r)+"<br>");
}
// Driver Code
let a=[1, 2, 2, 4];
let n = a.length;
performQueries(a, n);
// This code is contributed by rag2127
</script>
Producción:
-1 2
Complejidad de tiempo: O(M), donde M = RL es el número de elementos en el rango [L, R]
Nota: Dado que las restricciones de la pregunta eran muy menores, se aprobará una solución de fuerza bruta. La solución se puede optimizar aún más mediante un árbol de segmentos .