人口最多的年份
难度:
标签:
题目描述
代码结果
运行时间: 23 ms, 内存: 16.0 MB
/*
题目思路:
1. 使用Java Stream来简化操作。
2. 依然使用数组years记录人口变化,但使用Streams来处理数组操作。
3. 最后找到最大人口数及最早的年份。
*/
import java.util.stream.IntStream;
public class Solution {
public int maxPopulationYear(int[][] logs) {
int[] years = new int[101];
IntStream.range(0, logs.length).forEach(i -> {
years[logs[i][0] - 1950]++;
years[logs[i][1] - 1950]--;
});
int[] maxPopulation = {0};
int[] maxYear = {0};
int[] currentPopulation = {0};
IntStream.range(0, years.length).forEach(i -> {
currentPopulation[0] += years[i];
if (currentPopulation[0] > maxPopulation[0]) {
maxPopulation[0] = currentPopulation[0];
maxYear[0] = 1950 + i;
}
});
return maxYear[0];
}
}
解释
方法:
该题解采用了计数的方法来解决问题。首先,创建一个大小为100的数组(因为年份从1950到2049,共100年),用于记录每一年的人口数量。遍历每个人的生命记录,对于每个人,其在生存期间的每一年对应的数组位置增加1,表示那一年的人口增加了1。在更新完所有人的生存记录后,再遍历这个数组,找到人口最多的年份。如果有多个年份人口相同,由于是从最早的年份开始统计的,第一个找到的最大值将是最早的年份。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么选择使用大小为100的数组来记录每一年的人口数量,而不是使用哈希表或其他数据结构?
▷🦆
在计算每一个人的生存年份时,为什么可以直接使用`range(log[0], log[1])`,而不需要考虑边界年份是否包含在1950到2049之间?
▷🦆
在题解中提到的`人口最多的最早年份`的定义,是否意味着在相同人口数量的情况下,只关心第一次出现的年份而忽略后续的年份?
▷🦆
对于`res[year - 1950] += 1`这一操作,如果输入数据中存在错误,比如死亡年份早于出生年份,这种情况下题解是否还能正确处理?
▷