人口最多的年份

5750. 人口最多的年份

难度简单2收藏分享切换为英文接收动态反馈

给你一个二维整数数组 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

暴力统计

class Solution {
    public int maximumPopulation(int[][] logs) {

        int max = 0;
        int maxIndex = 1950;
        for (int i = 1950; i <= 2050; i++) {
            // 统计当前年份的人数
            int cnt = 0;
            // 统计在当前年份之前出生的人的数量
            for (int j = 0; j < logs.length; j++) {
                if (logs[j][0] <= i) {
                    cnt++;
                }
            }
            // 统计在当前年份之前死亡的人的数量
            for (int j = 0; j < logs.length; j++) {
                if (logs[j][1] <= i) {
                    cnt--;
                }
            }
			// 如果当前活着的人口的数量大于其他年份的数量,那么记录最大值的年份
            if (cnt > max) {
                max = cnt;
                maxIndex = i;
            }

        }
        return maxIndex;
    }
}

差分法

• 利用一个数组作为hash表记录当前年份出生的人的数量和死亡的人的数量
• 再次遍历哈希表找到最大值的年份

class Solution {
    public int maximumPopulation(int[][] logs) {
        int[] d = new int[110];
        for(int[] log : logs) {     //遍历每个人的出生和死亡年份
            d[log[0] - 1950] += 1;  //出生年份人数+1
            d[log[1] - 1950] -= 1;  //死亡年份人数-1
        }
        int s = 0, res = 0, cnt = 0;
        for(int i = 0; i <= 100; i++){
            s += d[i];      //s是记录每一年的存活人数
            if(s > cnt){
                cnt = s; 
                res = i;
            }
        }
        return res + 1950;
    }
}

作者：hpq30Fv0IV
链接：https://leetcode-cn.com/problems/maximum-population-year/solution/javabao-li-chai-fen-by-hpq30fv0iv-bupd/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

赏

谢谢你请我吃糖果

微信