Deklarata e Problemit

Zgjidhje LeetCode Viti i Popullsisë Maksimale thotë se – Ju jepet një grup me numra të plotë 2D logs ku secila logs[i] = [birth_i, death_i] tregon vitet e lindjes dhe të vdekjes së ith personi.

La popullsi prej disa vitesh x është numri i njerëzve të gjallë gjatë atij viti. Të ith një person llogaritet në vit x's popullsisë nëse x ndodhet ne përfshirë varg [birth_i, death_i - 1]. Vini re se personi është nuk llogariten në vitin kur vdesin.

Kthim Viti i popullsisë maksimale.

 

1 Shembull:

input:

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

output:

 1993

Shpjegim:

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

2 Shembull:

input:

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

output:

 1960

Shpjegim:

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

 

Kufizimet:

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

 

ALGORITMI -

• Për të gjetur vitin e popullsisë maksimale. Së pari, ne do të fokusohemi në numrin total të popullsisë në çdo vit duke kontrolluar në çdo interval të matricës së dhënë dhe do të gjejmë numërimin maksimal dhe do të kthejmë vitin e vlerës maksimale. Nëse numërimi është i njëjtë, atëherë thjesht kthejmë vitin e kaluar (vitin më të hershëm).

Qasja për vitin e popullsisë maksimale Zgjidhja LeetCode

– Së pari, ne do të krijojmë një grup me madhësi 101 sepse kufizimet e viteve qëndrojnë në intervalin 1950-2050.

– pas kësaj, ne do të ekzekutojmë një lak nga 0 në gjatësinë e regjistrave dhe do të rrisim numrin e grupit në indeks(logs[i][o]) me 1 dhe do të ulim numrin e grupit në indeks (logs[i ][1]) me 1

– përsëri do të ekzekutojmë një lak nga 0 në gjatësinë e grupit dhe do të bëjmë një numërim të një variabli prev dhe do të përditësojmë çdo element të grupit sipas grupit+prev dhe do të përditësojmë prev nga prev = array[i].

– më në fund, do të ekzekutojmë një lak dhe do të gjejmë vlerën maksimale në grup dhe do të kthejmë atë indeks të veçantë (indeks+1950). Prandaj gjeni vitin maksimal të popullsisë.

Code:

Zgjidhja e Python Leetcode për Vitin e Popullsisë Maksimale:

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

Zgjidhja e kodit Java Leetcode për Vitin e Popullsisë Maksimale:

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;
        
        
    }
}

Analiza e kompleksitetit të zgjidhjes së kodit Leet të Vitit të Popullsisë Maksimale:

Kompleksiteti i kohës

Kompleksiteti kohor i zgjidhjes së mësipërme është O(n).

Kompleksiteti i kohës

Kompleksiteti Hapësinor i zgjidhjes së mësipërme është O(1).

Siç kemi bërë një varg me gjatësi = 101. Pra, mund ta konsiderojmë konstante