leetcode
leetcode 1651 ~ 1700
人口最多的年份

人口最多的年份

难度:

标签:

题目描述

代码结果

运行时间: 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的数组来记录每一年的人口数量,而不是使用哈希表或其他数据结构?
选择使用大小为100的数组来记录每一年的人口数量是因为年份范围(1950到2049)是已知的且连续的,这使得数组可以通过简单的索引来访问对应年份的人口数量。数组的访问时间复杂度为O(1),这比哈希表的平均O(1)时间复杂度更为稳定且没有额外的哈希冲突处理开销。此外,数组因其连续内存分配,也优于哈希表在空间局部性方面的表现,这有助于提升缓存效率。
🦆
在计算每一个人的生存年份时,为什么可以直接使用`range(log[0], log[1])`,而不需要考虑边界年份是否包含在1950到2049之间?
题解中直接使用`range(log[0], log[1])`来计算每一个人的生存年份,基于假设输入数据始终有效,即所有的出生和死亡年份都严格在1950到2049范围内。如果实际应用需要处理边界外的年份,那么代码应该添加适当的边界检查以避免数组访问越界。但在这个特定问题的设定中,这样的检查被认为是不必要的,前提是输入数据遵循这一规范。
🦆
在题解中提到的`人口最多的最早年份`的定义,是否意味着在相同人口数量的情况下,只关心第一次出现的年份而忽略后续的年份?
是的,根据题解的逻辑,`人口最多的最早年份`的定义确实意味着如果存在多个年份人口数量相同,只关心最早出现的年份。这是通过在找到新的最大人口数量时立即更新年份实现的,而不是继续搜索可能出现相同人口数量的其他年份。这种方法确保了只记录第一次达到最大值的年份。
🦆
对于`res[year - 1950] += 1`这一操作,如果输入数据中存在错误,比如死亡年份早于出生年份,这种情况下题解是否还能正确处理?
题解中的`res[year - 1950] += 1`操作基于假定所有输入数据都是正确的,即每个人的死亡年份都晚于或等于其出生年份。如果输入数据中死亡年份早于出生年份,这将导致`range`函数生成一个空序列,因此不会执行任何加法操作,也不会引发错误。然而,这种情况在现实中可能表示输入数据本身存在问题,应该在实际应用中进行错误处理或数据验证。

相关问题