Problem bəyanat

Maksimum Əhali İli LeetCode Həlli deyir ki, – Sizə 2D tam massiv verilir logs harada logs[i] = [birth_i, death_i] doğum və ölüm illərini göstərir ith şəxs.

The bir ilin əhalisi x həmin il ərzində yaşayan insanların sayıdır. The ith adam ildə sayılır xnin əhalisi əgər x içindədir o cümlədən silsilə [birth_i, death_i - 1]. Qeyd edək ki, şəxs yox öldükləri ildə hesablanır.

Qayıtmaq Maksimum əhali ili.

 

Misal 1:

Input:

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

Çıxış:

 1993

Explanation:

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

Misal 2:

Input:

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

Çıxış:

 1960

Explanation:

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

 

Məhdudiyyətlər:

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

 

ALQORİTM -

• Maksimum Əhali İlini tapmaq üçün. Birincisi, biz verilmiş matrisin hər bir intervalında yoxlanaraq, hər il ərzində əhalinin ümumi sayına diqqət yetirəcəyik və maksimum sayı tapacaq və maksimum dəyər ilini qaytaracağıq. Əgər say eynidirsə, biz sadəcə əvvəlki ili (ən erkən il) qaytarırıq.

Maksimum Əhali İlinə yanaşma LeetCode Həlli

– Birincisi, biz 101 ölçülü bir massiv yaradacağıq, çünki illərin məhdudiyyətləri 1950 ilə 2050 arasındadır.

– bundan sonra biz 0-dan logların uzunluğuna qədər bir dövrə işlədəcəyik və index(logs[i][o])-da massivin sayını 1-ə qədər artıracağıq və indeksdəki (logs[i) massivin sayını azaldacağıq. ][1]) 1 ilə

– yenə biz 0-dan massivin uzunluğuna qədər bir döngə işlədəcəyik və bir dəyişən prev hesablayacağıq və massivin hər bir elementini massiv+prev ilə yeniləyəcəyik və əvvəlkini əvvəlki = massiv[i] ilə yeniləyəcəyik.

– nəhayət, bir döngə işlədəcəyik və massivdə maksimum dəyəri tapacağıq və həmin indeksi qaytaracağıq (index+1950). Beləliklə, maksimum əhali ilini tapın.

Kodu

Maksimum Əhali İli Python Leetcode Həlli:

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

Maksimum Əhali İli Java Leetcode Həlli:

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

Maksimum Əhali İlinin Mürəkkəblik Təhlili Leetcode Həll:

Zamanın mürəkkəbliyi

Yuxarıdakı məhlulun Zaman mürəkkəbliyi O(n)-dir.

Zamanın mürəkkəbliyi

Yuxarıdakı məhlulun Kosmik Mürəkkəbliyi O(1)-dir.

Uzunluğu = 101 massiv etdik. Beləliklə, onu sabit hesab edə bilərik