សេចក្តីថ្លែងការណ៍បញ្ហា។

ដំណោះស្រាយ LeetCode ឆ្នាំចំនួនប្រជាជនអតិបរមា និយាយថា - អ្នកត្រូវបានផ្តល់អារេចំនួនគត់ 2D logs ដែលជាកន្លែងដែលគ្នា logs[i] = [birth_i, death_i] បង្ហាញពីឆ្នាំកំណើតនិងមរណភាព ith មនុស្ស។

នេះ ចំនួនប្រជាជនក្នុងមួយឆ្នាំ x គឺជាចំនួនមនុស្សនៅរស់ក្នុងឆ្នាំនោះ។ នេះ។ ith មនុស្សម្នាក់ត្រូវបានរាប់ក្នុងឆ្នាំ xចំនួនប្រជាជនប្រសិនបើ x គឺស្ថិតនៅក្នុង រួមបញ្ចូល ជួរ [birth_i, death_i - 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 <= 100
• 1950 <= birth_i < death_i <= 2050

 

អាល់ហ្គោរីត -

• ដើម្បីស្វែងរកឆ្នាំចំនួនប្រជាជនអតិបរមា។ ជាដំបូង យើងនឹងផ្តោតលើចំនួនប្រជាជនសរុបក្នុងឆ្នាំនីមួយៗ ដោយពិនិត្យមើលចន្លោះពេលនីមួយៗនៃម៉ាទ្រីសដែលបានផ្តល់ឱ្យ ហើយនឹងរកឃើញចំនួនអតិបរមា និងត្រឡប់ឆ្នាំនៃតម្លៃអតិបរមា។ ប្រសិនបើចំនួនដូចគ្នានោះ យើងគ្រាន់តែត្រឡប់ឆ្នាំមុន (ឆ្នាំដំបូងបំផុត)។

វិធីសាស្រ្តសម្រាប់ឆ្នាំចំនួនប្រជាជនអតិបរមាដំណោះស្រាយ LeetCode

- ដំបូង យើងនឹងបង្កើតអារេមួយនៃទំហំ 101 ពីព្រោះឧបសគ្គនៃឆ្នាំស្ថិតនៅចន្លោះឆ្នាំ 1950 ដល់ឆ្នាំ 2050។

- បន្ទាប់ពីនោះ យើងនឹងដំណើរការរង្វិលជុំពី 0 ទៅប្រវែងនៃកំណត់ហេតុ ហើយនឹងបង្កើនចំនួនអារេនៅលិបិក្រម(logs[i][o]) ដោយ 1 និងបន្ថយចំនួនអារេនៅលិបិក្រម (logs[i] [1]) ដោយ 1

– ម្តងទៀត យើងនឹងដំណើរការរង្វិលជុំពី 0 ទៅប្រវែងនៃអារេ ហើយធ្វើការរាប់អថេរមួយជាមុន ហើយធ្វើបច្ចុប្បន្នភាពធាតុនីមួយៗនៃអារេដោយអារេ+prev ហើយធ្វើបច្ចុប្បន្នភាពមុនដោយ prev = អារេ[i]។

- ជាចុងក្រោយ យើងនឹងដំណើរការរង្វិលជុំមួយ ហើយស្វែងរកតម្លៃអតិបរមានៅក្នុងអារេ ហើយត្រឡប់សន្ទស្សន៍ជាក់លាក់នោះ (index+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. ដូច្នេះយើងអាចពិចារណាវាថេរ