1854. 人口最多的年份
1854. 人口最多的年份
题目
You are given a 2D integer array logs
where each logs[i] = [birthi, deathi]
indicates the birth and death years of the ith
person.
The population of some year x
is the number of people alive during that year. The ith
person is counted in year x
's population if x
is in the inclusive range [birthi, deathi - 1]
. Note that the person is not counted in the year that they die.
Return the earliest year with the maximum population.
Example 1:
Input: logs = [[1993,1999],[2000,2010]]
Output: 1993
Explanation: The maximum population is 1, and 1993 is the earliest year with this population.
Example 2:
Input: logs = [[1950,1961],[1960,1971],[1970,1981]]
Output: 1960
Explanation:
The maximum population is 2, and it had happened in years 1960 and 1970.
The earlier year between them is 1960.
Constraints:
1 <= logs.length <= 100
1950 <= birthi < deathi <= 2050
题目大意
给你一个二维整数数组 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
解题思路
定义数组:
- 定义一个大小是 101 的数组
arr
,因为从 1950 到 2050 一共 101 年(包括 1950 和 2050)。 arr[i]
存储的是1950 + i
年的人口变化(增减)。
- 定义一个大小是 101 的数组
人口变化记录:
- 对于每个人的出生年份
birth
,会在arr[birth - 1950]
位置上加 1,表示从birth
年开始人口增加。 - 对于每个人的死亡年份
death
,会在arr[death - 1950]
位置上减 1,表示从death
年起,人口减少(死亡是当年结束,所以处理的是death
年的结束)。
- 对于每个人的出生年份
计算最大人口:
- 遍历
arr
数组,计算每一年的总人口。 - 使用
population
来累积每一年的人口变化。 - 如果当前人口数
population
大于历史最大值max
,则更新max
和当前年份year
。
- 遍历
返回结果:最终,
year
就是人口最多的年份。
复杂度分析
- 时间复杂度:
O(n)
,其中n
是logs
数组的长度,需要先遍历每一条记录并更新arr
数组,然后再遍历一次arr
数组计算最大人口年份。 - 空间复杂度:
O(1)
,虽然使用了一个大小为 101 的数组,但它的大小是固定的,因此空间复杂度是常数级别的。
代码
/**
* @param {number[][]} logs
* @return {number}
*/
var maximumPopulation = function (logs) {
let arr = new Array(101).fill(0); // 用于存储每一年人口的增减情况
for (let [birth, death] of logs) {
arr[birth - 1950]++; // 出生年份人口增加
arr[death - 1950]--; // 死亡年份人口减少
}
let population = 0,
max = 0,
year = 1950;
for (let i = 0; i < arr.length; i++) {
population += arr[i]; // 计算每一年的总人口
if (population > max) {
// 更新最大人口和对应年份
max = population;
year = i + 1950; // 将数组索引转换为实际年份
}
}
return year; // 返回最大人口的年份
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 | 力扣 |
---|---|---|---|---|---|
2381 | 字母移位 II | 数组 字符串 前缀和 | 🟠 | 🀄️ 🔗 |