《程序员面试金典（第6版）面试题 16.10. 生存人数（前缀和思想）-Toy模板网

这篇具有很好参考价值的文章主要介绍了《程序员面试金典（第6版）面试题 16.10. 生存人数（前缀和思想）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目描述

给定 N 个人的出生年份和死亡年份，第 i 个人的出生年份为 birth[i]，死亡年份为 death[i]，实现一个方法以计算生存人数最多的年份。

你可以假设所有人都出生于 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;
    }
};

《程序员面试金典（第6版）面试题 16.10. 生存人数（前缀和思想）

复杂度分析

时间复杂度：

第一个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;
    }
};

《程序员面试金典（第6版）面试题 16.10. 生存人数（前缀和思想）

复杂度分析

时间复杂度分析：

第一个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)。

总结

这道题的意义主要在于考察编程者如何处理和分析一组数据，以找到满足特定条件的解。在这个问题中，我们需要找到生存人数最多的年份。

这个问题可以帮助编程者练习以下几个方面的技能：

数据处理：如何从给定的出生年份和死亡年份数据中提取有用的信息。
循环和条件判断：如何遍历数据并进行逻辑判断以计算在每个年份的生存人数。
状态累积：如何在遍历过程中累积生存人数，以便找到最大值和对应的年份。
优化和算法思维：如何从暴力解法转向更优秀的算法，比如前缀和方法，从而提高计算效率。

总的来说，这道题的意义在于让编程者思考如何高效地处理和分析数据，找到符合特定条件的解。通过这道题，编程者可以提升自己的编程能力、算法思维和问题解决技巧。
最后的最后，如果你觉得我的这篇文章写的不错的话，请给我一个赞与收藏，关注我，我会继续给大家带来更多更优质的干货内容。文章来源地址https://www.toymoban.com/news/detail-432334.html

到了这里，关于《程序员面试金典（第6版）面试题 16.10. 生存人数（前缀和思想）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！