题目描述
-
你可以假设所有人都出生于 1900 年至 2000 年（含 1900 和 2000 ）之间。如果一个人在某一年的任意时期处于生存状态，那么他应该被纳入那一年的统计中。例如，生于 1908 年、死于 1909 年的人应当被列入 1908 年和 1909 年的计数。
-
如果有多个年份生存人数相同且均为最大值，输出其中最小的年份。
示例：
输入：
birth = [1900, 1901, 1950]
death = [1948, 1951, 2000]
输出： 1901
提示：
- 0 < birth.length == death.length <= 10000
- birth[i] <= death[i]
解题思路与代码
这道题是一道中等偏简单的题。因为这道题我很快就有思路并且能较快的实现这道题，所以我把它归类为中等偏简单的题，hh。接下来来讲一下解题思路吧。
首先对于这道题来说，我们最重要的是要建立起一个数组，这个数组的作用其实就是去存储1900-2000年，每个年份存在的人数。
讲到这里相信大家心里应该有点数了，从这里，我们就可以衍生出两种做法，接下来，我们依次的循序渐进的介绍这两种方法。
方法一：累加，统计每一年的生存人数
-
在这种方法里，我们首先创建一个大小为101的age数组。目的是映射1900-2000年所有年份存活的人数。
-
之后我们用for循环遍历出生数组，并且用两个变量去记录当前这个人的出生年与死亡年都是多少。再用一个while循环去将age数组对应的年份的人数都+1
-
在之后，我们再遍历一次age数组，找出最多生存人数的年份就好。
具体代码如下：
class Solution {
public:
int maxAliveYear(vector<int>& birth, vector<int>& death) {
int age[101] = {0}; // 用来存储当前在世人数。
for(int i = 0; i < birth.size(); ++i){
int by = birth[i] - 1900;
int dy = death[i] - 1900;
while(by <= dy){
++age[by];
++by;
}
}
int maxPeople = 0;
int result = 0;
for(int i = 0; i < 101; ++i){
if(maxPeople < age[i]){
maxPeople = age[i];
result = i + 1900;
}
}
return result;
}
};
复杂度分析
时间复杂度：
- 第一个for循环遍历birth和death向量，复杂度为O(n)，其中n为birth和death向量的大小，即人数。
- 内部的while循环在最坏情况下，每个人都在整个时间段内活着，因此需要遍历整个年份范围（101年），那么最坏情况下复杂度为O(101)。
- 第二个for循环遍历age数组，复杂度为O(101)。
总的时间复杂度为：O(n * 101 + 101)。由于101是一个常数，因此我们可以忽略它，所以总的时间复杂度为O(n)。
空间复杂度：
- age数组的空间复杂度为O(101)。
- 其他变量（如maxPeople，result，by，dy等）都是常量级别的空间。
总的空间复杂度为O(101)。由于101是一个常数，我们可以忽略它，所以总的空间复杂度为O(1)。
方法二： 优化，前缀和思想解决累积和或累积统计的问题
-
这种方法的优化在于，优化掉了内在的while循环。与方法一的区别是，我们创建一个大小为102的age数组。为什么这么创建呢？是因为当一个人死亡的时候，它死亡的这一年也算它在这一年存在的。
-
我们在用for循环遍历的时候，如果有人在这一年出生了，我们就把这一年它对应的出生age元素+1，它对应的死亡age + 1元素 -1。这就是我们为什么要创建102数组的原因。因为一个人它在2000年死亡的时候，2001年才会记作它不存在。所以数组的大小为102。
-
最后我们在用一个for循环，去累加每一年的生存人数，然后去比较出一个最大生存人数的年份
具体的代码如下：
class Solution {
public:
int maxAliveYear(vector<int>& birth, vector<int>& death) {
int delta[102] = {0}; // 存储每年人口变化
for (int i = 0; i < birth.size(); ++i) {
delta[birth[i] - 1900]++; // 出生年份人数加一
delta[death[i] - 1900 + 1]--; // 死亡年份的下一年人数减一
}
int maxPeople = 0;
int currentAlive = 0;
int result = 0;
for (int i = 0; i < 101; ++i) {
currentAlive += delta[i]; // 计算当前年份的生存人数
if (currentAlive > maxPeople) {
maxPeople = currentAlive;
result = i + 1900;
}
}
return result;
}
};
复杂度分析
时间复杂度分析：
- 第一个for循环遍历birth和death向量，复杂度为O(n)，其中n为birth和death向量的大小，即人数。
- 第二个for循环遍历age数组，复杂度为O(101)。
总的时间复杂度为：O(n + 101)。由于101是一个常数，我们可以忽略它，所以总的时间复杂度仍为O(n)。相比原始代码，时间复杂度没有改变，但实际计算量减少了很多。
空间复杂度分析：
- age数组的空间复杂度为O(102)。
- 其他变量（如max，curr，result等）都是常量级别的空间。
总的空间复杂度为O(102)。由于102是一个常数，我们可以忽略它，所以总的空间复杂度仍为O(1)。
总结
这个问题可以帮助编程者练习以下几个方面的技能：
- 数据处理：如何从给定的出生年份和死亡年份数据中提取有用的信息。
- 循环和条件判断：如何遍历数据并进行逻辑判断以计算在每个年份的生存人数。
- 状态累积：如何在遍历过程中累积生存人数，以便找到最大值和对应的年份。
- 优化和算法思维：如何从暴力解法转向更优秀的算法，比如前缀和方法，从而提高计算效率。
总的来说，这道题的意义在于让编程者思考如何高效地处理和分析数据，找到符合特定条件的解。通过这道题，编程者可以提升自己的编程能力、算法思维和问题解决技巧。
最后的最后，如果你觉得我的这篇文章写的不错的话，请给我一个赞与收藏，关注我，我会继续给大家带来更多更优质的干货内容。