Planteamiento del problema
Máxima Población Año Solución LeetCode dice que: se le da una matriz de enteros 2D logs donde cada logs[i] = [birthi, deathi] indica los años de nacimiento y muerte del ith persona.
La población de algún año x es el número de personas vivas durante ese año. los ith una persona se cuenta en el año xla población si x está en el incluso distancia [birthi, deathi - 1]. Tenga en cuenta que la persona es no contados en el año en que mueren.
Regreso la Población Máxima Año.
Ejemplo 1:
Entrada:
logs = [[1993,1999],[2000,2010]]
Salida:
1993
Explicación:
The maximum population is 1, and 1993 is the earliest year with this population.
Ejemplo 2:
Entrada:
logs = [[1950,1961],[1960,1971],[1970,1981]]
Salida:
1960
Explicación:
The maximum population is 2, and it had happened in years 1960 and 1970. So the maximum population year is 1960.
Restricciones:
1 <= logs.length <= 1001950 <= birthi< deathi<= 2050
ALGORITMO –
- Para Encontrar el Año de Máxima Población. Primero, nos enfocaremos en el número total de población en cada año revisando cada intervalo de la matriz dada y encontraremos el recuento máximo y devolveremos el año de valor máximo. Si el recuento es el mismo, simplemente devolvemos el año anterior (primer año).
Enfoque para la solución LeetCode del año de población máxima
– Primero, crearemos una matriz de tamaño 101 porque las restricciones de años se encuentran en el rango de 1950 a 2050.
– después de eso, ejecutaremos un ciclo desde 0 hasta la longitud de los registros y aumentaremos el conteo de la matriz en el índice (logs[i][o]) en 1 y disminuiremos el conteo de la matriz en el índice (logs[i ][1]) por 1
– de nuevo ejecutaremos un ciclo desde 0 hasta la longitud de la matriz y haremos que una variable prev cuente y actualice cada elemento de la matriz por matriz+prev y actualice prev por prev = matriz[i].
– por último, ejecutaremos un ciclo y encontraremos el valor máximo en la matriz y devolveremos ese índice en particular (índice + 1950). Por lo tanto, encuentre el año de máxima población.
Código:
Año de población máxima Solución Python Leetcode:
class Solution:
def maximumPopulation(self, logs: List[List[int]]) -> int:
arr = [0]*101
for i in range(len(logs)):
arr[logs[i][0]-1950] += 1
arr[logs[i][1]-1950] -= 1
previous = arr[0]
for i in range(1,101):
arr[i] += previous
previous = arr[i]
print(arr)
maxi = 0
ind = 0
for i in range(len(arr)):
if arr[i] > maxi:
maxi = arr[i]
ind = i + 1950
print(maxi)
return ind
Año de población máxima Solución Java Leetcode:
class Solution {
public int maximumPopulation(int[][] logs) {
int[] arr = new int[101];
for(int i = 0;i < logs.length;i++){
arr[logs[i][0]-1950] +=1;
arr[logs[i][1]-1950] -=1;
}
int prev = arr[0];
for(int i=1;i<arr.length;i++){
arr[i] += prev;
prev = arr[i];
}
int ind = 0;
int maxi = 0;
for(int i=0;i<arr.length;i++){
if(maxi < arr[i]){
maxi = arr[i];
ind = i+1950;
}
}
return ind;
}
}
Análisis de Complejidad de la Solución Leetcode del Año Máximo de Población:
Complejidad de tiempo
La complejidad temporal de la solución anterior es O(n).
Complejidad de tiempo
La complejidad espacial de la solución anterior es O(1).
Como hemos hecho una matriz de longitud = 101. Entonces podemos considerarlo constante