1854. 人口最多的年份

🟢 🔖 数组 计数 前缀和 🔗 力扣open in new window LeetCodeopen in new window

题目

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 年的人口变化（增减）。
人口变化记录：
- 对于每个人的出生年份 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; // 返回最大人口的年份
};

1854. 人口最多的年份

# 1854. 人口最多的年份

# 题目

# 题目大意

# 解题思路

# 复杂度分析

# 代码

# 相关题目

1854. 人口最多的年份

题目

题目大意

解题思路

复杂度分析

代码

相关题目