Проблемалық мәлімдеме
Ең көп халық саны LeetCode шешімі былай дейді – Сізге 2D бүтін массив беріледі logs қайда logs[i] = [birthi, deathi] туған және өлген жылдарын көрсетеді ith адам.
The бір жылғы халық x - сол жылдағы тірі адамдар саны. The ith адам жылы есептеледі xхалқының саны, егер x орналасқан инклюзивті диапазон [birthi, deathi - 1]. адам екенін ескеріңіз емес олар өлген жылы есептеледі.
қайтару Ең көп халық саны.
Мысал 1:
Кіру:
logs = [[1993,1999],[2000,2010]]
Шығару:
1993
Түсіндіру:
The maximum population is 1, and 1993 is the earliest year with this population.
Мысал 2:
Кіру:
logs = [[1950,1961],[1960,1971],[1970,1981]]
Шығару:
1960
Түсіндіру:
The maximum population is 2, and it had happened in years 1960 and 1970. So the maximum population year is 1960.
Шектеулер:
1 <= logs.length <= 1001950 <= birthi< deathi<= 2050
АЛГОРИТМ –
- Ең көп қоныстанған жылды табу үшін. Біріншіден, біз берілген матрицаның әрбір интервалын тексеру арқылы әр жылдағы жалпы халық санына назар аударамыз және максималды санды табамыз және максималды мән жылын қайтарамыз. Егер сан бірдей болса, біз жай ғана өткен жылды қайтарамыз (ең ерте жыл).
Ең көп қоныстанған жыл тәсілі LeetCode шешімі
– Біріншіден, біз 101 өлшемді бір массив жасаймыз, өйткені жылдар шектеулері 1950 мен 2050 аралығында болады.
– содан кейін біз 0-ден журналдардың ұзындығына дейін циклды орындаймыз және index(logs[i][o]) массивінің санын 1-ге көбейтеміз және индекстегі массивтің санын азайтамыз (logs[i ][1]) 1 бойынша
– қайтадан біз 0-ден массив ұзындығына дейін циклды орындаймыз және бір айнымалыны prev санайтын етіп жасаймыз және массивтің әрбір элементін array+prev арқылы жаңартамыз және prev prev = array[i] арқылы жаңартамыз.
– соңында біз циклды орындаймыз және массивтегі максималды мәнді табамыз және нақты индексті қайтарамыз (индекс+1950). Демек, ең үлкен халық жылын табыңыз.
Код:
Ең көп халық саны 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
Ең көп халық саны 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;
}
}
Ең көп қоныстанған жыл Leetcode шешімін күрделілік талдауы:
Уақыттың күрделілігі
Жоғарыдағы шешімнің уақыт күрделілігі O(n).
Уақыттың күрделілігі
Жоғарыдағы шешімнің кеңістіктік күрделілігі O(1).
Ұзындығы = 101 массивін жасағандықтан, оны тұрақты деп санауға болады