Постановка задачи

Максимальное количество населения в год Решение LeetCode говорит, что - Вам дан двумерный целочисленный массив logs где каждый logs[i] = [birth_i, death_i] указывает годы рождения и смерти ith человек.

Игровой автомат население какого-то года х - количество людей, живущих в течение этого года. ith человек исчисляется в году xнаселение России, если x находится в в том числе ассортимент [birth_i, death_i - 1]. Обратите внимание, что человек не учитываются в год, в котором они умирают.

Return Максимальная численность населения Год.

 

Пример 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 подсчетом и обновим каждый элемент массива с помощью array+prev и обновим prev с помощью prev = array[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. Значит, мы можем считать его постоянным