Dada una array ordenada de caracteres arr[] y un carácter K , la tarea es encontrar el carácter con el valor ASCII más pequeño más cercano que K de la array dada. Imprima -1 si no se encuentra ningún carácter que tenga un valor ASCII más pequeño que K .
Ejemplos:
Entrada: arr[] = {‘e’, ‘g’, ‘t’, ‘y’}, K = ‘u’
Salida: t
Explicación:
El carácter con el valor ASCII más pequeño más cercano a partir de ‘u’ es ‘t’ .
Entrada: arr[] = {‘e’, ‘g’, ‘t’, ‘y’}, K = ‘a’
Salida: -1
Explicación:
No existe ningún carácter con un valor ASCII menor que el de ‘a’.
Enfoque ingenuo:
el enfoque más simple para resolver el problema es iterar sobre la array y encontrar el carácter que tiene un valor ASCII más pequeño que el de K y la diferencia entre sus valores ASCII es mínima.
Complejidad de tiempo: O(N)
Espacio auxiliar: O(1)
Enfoque eficiente:
La idea es utilizar la búsqueda binaria para encontrar el elemento de piso (el carácter más grande es solo más pequeño que la tecla). Siga los pasos a continuación para resolver el problema:
- Realice una búsqueda binaria en la array.
- Compruebe si el elemento medio actual ( mid ) es igual al carácter K o no.
- Si es así, establezca start to mid – 1 , porque necesitamos encontrar un elemento más pequeño.
- Si el arr[mid] es más pequeño que K , guárdelo en alguna variable, digamos ch . Establezca start to mid + 1 para buscar un carácter más pequeño más cercano a K .
- De lo contrario, establezca end en mid-1 .
- Sigue repitiendo los pasos anteriores. Finalmente, imprime el carácter obtenido después de completar la búsqueda. Si no se obtiene ningún carácter, 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 return the
// nearest smaller character
char bs(char ar[], int n, int ele)
{
int start = 0;
int end = n - 1;
// Stores the nearest smaller
// character
char ch = '@';
// Iterate till starts cross end
while (start <= end) {
// Find the mid element
int mid = start + (end - start) / 2;
// Check if K is found
if (ar[mid] == ele)
end = mid - 1;
// Check if current character
// is less than K
else if (ar[mid] < ele) {
ch = ar[mid];
// Increment the start
start = mid + 1;
}
// Otherwise
else
// Increment end
end = mid - 1;
}
// Return the character
return ch;
}
// Driver Code
int main()
{
char ar[] = { 'e', 'g', 't', 'y' };
int n = sizeof(ar) / sizeof(ar[0]);
char K = 'u';
char ch = bs(ar, n, K);
if (ch == '@')
cout << "-1";
else
cout << ch;
return 0;
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
// Function to return the
// nearest smaller character
static char bs(char ar[], int n, int ele)
{
int start = 0;
int end = n - 1;
// Stores the nearest smaller
// character
char ch = '@';
// Iterate till starts cross end
while (start <= end)
{
// Find the mid element
int mid = start + (end - start) / 2;
// Check if K is found
if (ar[mid] == ele)
end = mid - 1;
// Check if current character
// is less than K
else if (ar[mid] < ele)
{
ch = ar[mid];
// Increment the start
start = mid + 1;
}
// Otherwise
else
// Increment end
end = mid - 1;
}
// Return the character
return ch;
}
// Driver Code
public static void main(String[] args)
{
char ar[] = { 'e', 'g', 't', 'y' };
int n = ar.length;
char K = 'u';
char ch = bs(ar, n, K);
if (ch == '@')
System.out.print("-1");
else
System.out.print(ch);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program to implement
# the above approach
# Function to return the
# nearest smaller character
def bs(a, n, ele):
start = 0
end = n - 1
# Stores the nearest smaller
# character
ch = '@'
# Iterate till starts cross end
while (start <= end):
# Find the mid element
mid = start + (end - start) // 2;
# Check if K is found
if(ar[mid] == ele):
end = mid - 1
# Check if current character
# is less than K
elif(ar[mid] < ele):
ch = ar[mid]
# Increment the start
start = mid + 1;
# Otherwise
else:
# Increment end
end = mid - 1;
# Return the character
return ch
# Driver code
if __name__=='__main__':
ar = [ 'e', 'g', 't', 'y' ]
n = len(ar)
K = 'u';
ch = bs(ar, n, K);
if (ch == '@'):
print('-1')
else:
print(ch)
# This code is contributed by rutvik_56
C#
// C# program to implement
// the above approach
using System;
class GFG{
// Function to return the
// nearest smaller character
static char bs(char []ar, int n, int ele)
{
int start = 0;
int end = n - 1;
// Stores the nearest smaller
// character
char ch = '@';
// Iterate till starts cross end
while (start <= end)
{
// Find the mid element
int mid = start + (end - start) / 2;
// Check if K is found
if (ar[mid] == ele)
end = mid - 1;
// Check if current character
// is less than K
else if (ar[mid] < ele)
{
ch = ar[mid];
// Increment the start
start = mid + 1;
}
// Otherwise
else
// Increment end
end = mid - 1;
}
// Return the character
return ch;
}
// Driver Code
public static void Main(String[] args)
{
char []ar = { 'e', 'g', 't', 'y' };
int n = ar.Length;
char K = 'u';
char ch = bs(ar, n, K);
if (ch == '@')
Console.Write("-1");
else
Console.Write(ch);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program for the above approach
// Function to return the
// nearest smaller letacter
function bs(ar, n, ele)
{
let start = 0;
let end = n - 1;
// Stores the nearest smaller
// letacter
let ch = '@';
// Iterate till starts cross end
while (start <= end)
{
// Find the mid element
let mid = start + Math.floor((end - start) / 2);
// Check if K is found
if (ar[mid] == ele)
end = mid - 1;
// Check if current letacter
// is less than K
else if (ar[mid] < ele)
{
ch = ar[mid];
// Increment the start
start = mid + 1;
}
// Otherwise
else
// Increment end
end = mid - 1;
}
// Return the letacter
return ch;
}
// Driver Code
let ar = [ 'e', 'g', 't', 'y' ];
let n = ar.length;
let K = 'u';
let ch = bs(ar, n, K);
if (ch == '@')
document.write("-1");
else
document.write(ch);
// This code is contributed by sanjoy_62.
</script>
t
Complejidad temporal: O(logN)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por shauryarehangfg y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA