Izjava o problemu
Maksimalna godina stanovništva LeetCode rješenje kaže da – Dat vam je 2D niz cijelih brojeva logs gdje svaki logs[i] = [birthi, deathi] označava godine rođenja i smrti ith osoba.
The populacija od neke godine x je broj ljudi živih tokom te godine. The ith osoba se računa u godini x's stanovništvo ako x je u uključujući domet [birthi, deathi - 1]. Imajte na umu da osoba jeste ne računa se u godinu u kojoj su umrli.
povratak Maksimalna godina stanovništva.
Primer 1:
Ulaz:
logs = [[1993,1999],[2000,2010]]
Izlaz:
1993
Objašnjenje:
The maximum population is 1, and 1993 is the earliest year with this population.
Primer 2:
Ulaz:
logs = [[1950,1961],[1960,1971],[1970,1981]]
Izlaz:
1960
Objašnjenje:
The maximum population is 2, and it had happened in years 1960 and 1970. So the maximum population year is 1960.
Ograničenja:
1 <= logs.length <= 1001950 <= birthi< deathi<= 2050
ALGORITAM –
- Da biste pronašli maksimalnu godinu stanovništva. Prvo ćemo se fokusirati na ukupnu brojnu populaciju u svakoj godini tako što ćemo provjeriti svaki interval date matrice i pronaći maksimalan broj i vratiti godinu maksimalne vrijednosti. Ako je broj isti onda jednostavno vraćamo prethodnu godinu (najranija godina).
Pristup za maksimalnu godinu stanovništva LeetCode rješenje
– Prvo ćemo napraviti jedan niz veličine 101 jer ograničenja godina leže u rasponu od 1950. do 2050. godine.
– nakon toga ćemo pokrenuti petlju od 0 do dužine dnevnika i povećati broj niza na indeksu (logs[i][o]) za 1 i smanjiti broj niza na indeksu (logs[i ][1]) od 1
– ponovo ćemo pokrenuti petlju od 0 do dužine niza i napraviti jednu varijablu prev count i ažurirati svaki element niza pomoću array+prev i update prev by prev = array[i].
– konačno ćemo pokrenuti petlju i pronaći maksimalnu vrijednost u nizu i vratiti taj određeni indeks (indeks+1950). Stoga pronađite maksimalnu godinu stanovništva.
Kod:
Maksimalna godina stanovništva Python Leetcode rješenje:
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
Maksimalna godina stanovništva Java Leetcode rješenje:
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 složenosti maksimalne godine stanovništva Leetcode rješenje:
Složenost vremena
Vremenska složenost gornjeg rješenja je O(n).
Složenost vremena
Prostorna složenost gornjeg rješenja je O(1).
Kako smo napravili niz dužine = 101. Tako da ga možemo smatrati konstantnim
