Easy

题目描述

给你一个二维整数数组 logs，其中每个 logs[i] = [birthi, deathi] 表示第 i 个人的出生和死亡年份。

年份 x 的 人口数 是这一年度活着的人的数目。第 i 个人被计入年份 x 的人口数当且仅当 x 在 闭区间 [birthi, deathi - 1] 内。注意，人不应当计入他们死亡当年的人口数。

返回 人口数最多 且 最早 的年份。

示例 1：

输入：logs = [[1993,1999],[2000,2010]]
输出：1993
解释：最大人口数为 1 ，而 1993 是人口数为 1 的最早年份。

示例 2：

输入：logs = [[1950,1961],[1960,1971],[1970,1981]]
输出：1960
解释：
最大人口数为 2 ，分别出现在 1960 和 1970 。
其中最早年份是 1960 。

提示：

  • 1 <= logs.length <= 100
  • 1950 <= birthi < deathi <= 2050

解题思路

这道题需要找出人口数最多的年份。我们可以用以下几种方法：

方法一：差分数组（推荐） 利用差分数组的思想，对于每个人的生命周期 [birth, death-1]，我们在 birth 位置 +1，在 death 位置 -1。然后计算前缀和就能得到每年的人口数。由于年份范围固定在 1950-2050，可以用数组直接映射。

方法二：暴力枚举 对于每个可能的年份，遍历所有人的记录，统计该年份的人口数。时间复杂度较高但思路简单。

方法三：事件扫描线 将所有出生和死亡事件按年份排序，然后扫描处理。出生事件人口+1，死亡事件人口-1。

差分数组方法最优，因为年份范围有限，可以充分利用数组的随机访问特性，时间复杂度为 O(n)，其中 n 是人数。

代码实现

class Solution {
public:
    int maximumPopulation(vector<vector<int>>& logs) {
        vector<int> diff(101, 0); // 1950-2050 范围
        
        // 构建差分数组
        for (auto& log : logs) {
            diff[log[0] - 1950]++;     // 出生年份 +1
            diff[log[1] - 1950]--;     // 死亡年份 -1
        }
        
        // 计算前缀和并找最大值
        int maxPop = 0, maxYear = 1950;
        int currentPop = 0;
        
        for (int i = 0; i < 101; i++) {
            currentPop += diff[i];
            if (currentPop > maxPop) {
                maxPop = currentPop;
                maxYear = 1950 + i;
            }
        }
        
        return maxYear;
    }
};

class Solution:
    def maximumPopulation(self, logs: List[List[int]]) -> int:
        diff = [0] * 101  # 1950-2050 范围
        
        # 构建差分数组
        for birth, death in logs:
            diff[birth - 1950] += 1   # 出生年份 +1
            diff[death - 1950] -= 1   # 死亡年份 -1
        
        # 计算前缀和并找最大值
        max_pop = 0
        max_year = 1950
        current_pop = 0
        
        for i in range(101):
            current_pop += diff[i]
            if current_pop > max_pop:
                max_pop = current_pop
                max_year = 1950 + i
        
        return max_year

public class Solution {
    public int MaximumPopulation(int[][] logs) {
        int[] diff = new int[101]; // 1950-2050 范围
        
        // 构建差分数组
        foreach (var log in logs) {
            diff[log[0] - 1950]++;     // 出生年份 +1
            diff[log[1] - 1950]--;     // 死亡年份 -1
        }
        
        // 计算前缀和并找最大值
        int maxPop = 0, maxYear = 1950;
        int currentPop = 0;
        
        for (int i = 0; i < 101; i++) {
            currentPop += diff[i];
            if (currentPop > maxPop) {
                maxPop = currentPop;
                maxYear = 1950 + i;
            }
        }
        
        return maxYear;
    }
}

var maximumPopulation = function(logs) {
    const diff = new Array(101).fill(0); // 1950-2050 范围
    
    // 构建差分数组
    for (const [birth, death] of logs) {
        diff[birth - 1950]++;     // 出生年份 +1
        diff[death - 1950]--;     // 死亡年份 -1
    }
    
    // 计算前缀和并找最大值
    let maxPop = 0, maxYear = 1950;
    let currentPop = 0;
    
    for (let i = 0; i < 101; i++) {
        currentPop += diff[i];
        if (currentPop > maxPop) {
            maxPop = currentPop;
            maxYear = 1950 + i;
        }
    }
    
    return maxYear;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大小
时间复杂度O(n + k)，其中 n 是人数，k 是年份范围（101）
空间复杂度O(k)，差分数组的空间，k = 101

相关题目