英文网站建设 淮安,网页制作代码成品,网站分析报告怎么做,长沙定制网站开发题目#xff1a;
给定 N 个人的出生年份和死亡年份#xff0c;第 i 个人的出生年份为 birth[i]#xff0c;死亡年份为 death[i]#xff0c;实现一个方法以计算生存人数最多的年份。
你可以假设所有人都出生于 1900 年至 2000 年#xff08;含 1900 和 2000 #xff09;…题目
给定 N 个人的出生年份和死亡年份第 i 个人的出生年份为 birth[i]死亡年份为 death[i]实现一个方法以计算生存人数最多的年份。
你可以假设所有人都出生于 1900 年至 2000 年含 1900 和 2000 之间。如果一个人在某一年的任意时期处于生存状态那么他应该被纳入那一年的统计中。例如生于 1908 年、死于 1909 年的人应当被列入 1908 年和 1909 年的计数。
如果有多个年份生存人数相同且均为最大值输出其中最小的年份。
示例 输入 birth [1900, 1901, 1950] death [1948, 1951, 2000] 输出 1901 解题思路
年份生存人数也就相当于是对每个年龄段的两头进行记录找每个区间的重叠部分返回重叠的最大值。
这里我们用到差分数组出生年份的下标1死亡年份的下标-1 Code
class Solution {
public:int maxAliveYear(vectorint birth, vectorint death) {int n birth.size();vectorint diff(2002, 0); // 定义差分数组diff//先将每个年龄段的两头确定出来出生年份1死亡年份-1for (int i 0; i n; i){int x birth[i], y death[i];diff[x] 1; diff[y1]-1; // 表示对区间[x, y]的元素全部加一}int max 0, idx 0, sum(0);//计算差分数组的前缀和每一个前缀和对应问题的每一个位置的人数for (int i 1900; i 2000; i) {sum diff[i];//更新生存人数最多的年份不加等号就默认多个年份生存人数相同且均为最大值输出其中最小的年份if (max sum){max sum; idx i;}}return idx;}
};
