Declaración do problema

Ano de poboación máxima Solución LeetCode di que: recibes unha matriz de enteiros 2D logs onde cada un logs[i] = [birth_i, death_i] indica os anos de nacemento e morte do ith persoa.

o poboación dun ano x é o número de persoas vivas durante ese ano. O ith unha persoa cóntase no ano xa poboación de se x está no incluso alcance [birth_i, death_i - 1]. Teña en conta que a persoa é non contados no ano en que morren.

retorno o Ano de poboación máxima.

 

Exemplo 1:

Entrada:

 logs = [[1993,1999],[2000,2010]]

saída:

 1993

Explicación:

 The maximum population is 1, and 1993 is the earliest year with this population.

Exemplo 2:

Entrada:

 logs = [[1950,1961],[1960,1971],[1970,1981]]

saída:

 1960

Explicación:

 
The maximum population is 2, and it had happened in years 1960 and 1970.
So the maximum population year is 1960.

 

Restricións:

• 1 <= logs.length <= 100
• 1950 <= birth_i < death_i <= 2050

 

ALGORITMO -

• Co fin de atopar o ano de poboación máxima. En primeiro lugar, centrarémonos no número total de poboación de cada ano comprobando cada intervalo da matriz dada e atoparemos o reconto máximo e devolveremos o ano de valor máximo. Se o reconto é o mesmo, simplemente devolvemos o ano anterior (o ano máis antigo).

Enfoque para o ano de poboación máxima Solución LeetCode

– En primeiro lugar, crearemos unha matriz de tamaño 101 porque as limitacións dos anos están no intervalo de 1950 a 2050.

– despois diso, executaremos un bucle de 0 ata a lonxitude dos rexistros e aumentaremos o reconto da matriz en index(logs[i][o]) en 1 e diminuiremos o reconto da matriz no índice (logs[i ][1]) por 1

– de novo executaremos un bucle desde 0 ata a lonxitude da matriz e faremos que unha variable prev conte e actualizaremos cada elemento da matriz mediante array+prev e actualizaremos prev by prev = array[i].

– por fin, executaremos un bucle e atoparemos o valor máximo na matriz e devolveremos ese índice en particular (índice+1950). Polo tanto, atopar o ano máximo de poboación.

código:

Ano de poboació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

Ano de poboació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álise de complexidade do ano de poboación máxima Solución Leetcode:

Complexidade do tempo

A complexidade temporal da solución anterior é O(n).

Complexidade do tempo

A complexidade espacial da solución anterior é O(1).

Como fixemos unha matriz de lonxitude = 101. Así que podemos considerala constante