Dada una array arr[] que consta de N strings y una array Query[] que consta de Q consultas. Cada string en los arreglos arr[] y Query[] tiene la forma D/M/Y donde D , M e Y denotan la fecha, el mes y el año. Para cada consulta, la tarea es imprimir la siguiente fecha más cercana de la array dada arr[] . Si no existe tal fecha, escriba “-1” .
Ejemplos:
Entrada: arr[]={“22/4/1233”, “1/3/633”, “23/5/56645”, “4/12/233”}, Q = 2,
Consulta[] = {“ 23/3/4345”, “12/3/2”}
Salida:
23/5/56645
4/12/233
Explicación:
Consulta 1: La fecha más cercana después de “23/3/4345” es “23/5/56645 ”.
Consulta 2: La fecha más cercana después de «12/3/2» es «4/12/233».Entrada: arr[]={“22/4/1233”, “4/12/233”, “1/3/633”, “23/5/56645”}, Q = 1,
Consulta[] = {“ 4/4/34234234”}
Salida: -1
Enfoque ingenuo: el enfoque más simple para cada consulta en la array Query[] es recorrer la array arr[] y para cada fecha, verificar si es mayor que la fecha actual o no y si es la más cercana o no. Después de completar el recorrido de la array, imprima la fecha más cercana obtenida. Si no se encuentra ninguna fecha, imprima -1 .
Complejidad temporal: O(N*Q)
Espacio auxiliar: O(1)
Enfoque eficiente: la idea es ordenar la array dada arr[] usando una función de comparación . Luego use una búsqueda binaria para encontrar la fecha futura más cercana a cada fecha en Query[] . Siga los pasos a continuación para resolver el problema:
- Ordene la array de fechas arr[] comparando primero el año , luego el mes y luego el día .
- Después de ordenar la array en el paso anterior, para cada consulta, encuentre la fecha más cercana usando la búsqueda binaria para comparar dos fechas usando la función de comparación.
- Si no se encuentra una fecha válida, imprima “-1” .
- De lo contrario, imprima la fecha más cercana encontrada.
A continuación se muestra la implementación del enfoque anterior:
Java
// Java program for the above approach
import java.awt.*;
import java.io.*;
import java.util.*;
class GFG {
// Comparator function to compare
// the two dates
public static int comp(String s,
String t)
{
// Split the dates strings
// when a "/" found
String[] ss = s.split("/");
String[] tt = t.split("/");
int date1[] = new int[3];
int date2[] = new int[3];
// Store the dates in form
// of arrays
for (int i = 0; i < 3; i++) {
date1[i]
= Integer.parseInt(ss[i]);
date2[i]
= Integer.parseInt(tt[i]);
}
// If years are not same
if (date1[2] != date2[2]) {
return date1[2] - date2[2];
}
// If months are not same
else if (date1[1] != date2[1]) {
return date1[1] - date2[1];
}
// If days are not same
else if (date1[0] != date2[0]) {
return date1[0] - date2[0];
}
// If two date is same
return 0;
}
// Function to print the next
// closest date
public static String
nextClosestDate(String arr[],
String q)
{
// Sort date array
Arrays.sort(arr,
new Comparator<String>() {
@Override
public int compare(String o1,
String o2)
{
return comp(o1, o2);
}
});
// Perform the Binary search
// to answer the queries
int l = 0, r = arr.length - 1;
int ind = -1;
// Iterate until l <= r
while (l <= r) {
// Find mid m
int m = (l + r) / 2;
// Comparator function call
int c = comp(q, arr[m]);
// If comp function return 0
// next closest date is found
if (c == 0) {
ind = m;
break;
}
// If comp function return
// less than 0, search in
// the left half
else if (c < 0) {
r = m - 1;
ind = m;
}
// If comp function return
// greater than 0, search
// in the right half
else {
l = m + 1;
}
}
// Return the result
if (ind == -1) {
return "-1";
}
else {
return arr[ind];
}
}
public static void
performQueries(String[] arr,
String[] Q)
{
// Traverse the queries of date
for (int i = 0; i < Q.length; i++) {
// Function Call
System.out.println(
nextClosestDate(arr, Q[i]));
}
}
// Driver Code
public static void main(String[] args)
{
// Given array of dates
String arr[] = { "22/4/1233",
"1/3/633",
"23/5/56645",
"4/12/233" };
// Given Queries
String Q[]
= { "23/3/4345",
"4/4/34234234",
"12/3/2" };
// Function Call
performQueries(arr, Q);
}
}
23/5/56645 -1 4/12/233
Complejidad de tiempo: O((N*log N) + (Q*log N))
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por adarsh000321 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA