跳至主要內容

1854. 人口最多的年份


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

解题思路

  1. 定义数组

    • 定义一个大小是 101 的数组 arr,因为从 1950 到 2050 一共 101 年(包括 1950 和 2050)。
    • arr[i] 存储的是 1950 + i 年的人口变化(增减)。
  2. 人口变化记录

    • 对于每个人的出生年份 birth,会在 arr[birth - 1950] 位置上加 1,表示从 birth 年开始人口增加。
    • 对于每个人的死亡年份 death,会在 arr[death - 1950] 位置上减 1,表示从 death 年起,人口减少(死亡是当年结束,所以处理的是 death 年的结束)。
  3. 计算最大人口

    • 遍历 arr 数组,计算每一年的总人口。
    • 使用 population 来累积每一年的人口变化。
    • 如果当前人口数 population 大于历史最大值 max,则更新 max 和当前年份 year
  4. 返回结果:最终,year 就是人口最多的年份。

复杂度分析

  • 时间复杂度O(n),其中 nlogs 数组的长度,需要先遍历每一条记录并更新 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数组 字符串 前缀和🟠🀄️open in new window 🔗open in new window