面试题 16.10. 生存人数-差分数组

面试题 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

这次也只是博主第二次使用差分数组，差分数组是一个非常帮的算法，可以极大的帮助我们解决区间统计的问题，感兴趣，可以学习一下，解题代码如下：

int maxAliveYear(int* birth, int birthSize, int* death, int deathSize){
    int year_surive[10001];
    for(int i=0;i<10001;i++){
        year_surive[i]=0;
    }
    for(int i=0;i<birthSize;i++){
        year_surive[birth[i]]++;
        year_surive[death[i]+1]--;

    }
    for(int i=1;i<10001;i++){
       year_surive[i]=year_surive[i-1]+year_surive[i];
    }
    int year_re=0, max=0;
    for(int i=1;i<10001;i++){
       if(year_surive[i]>max){
           year_re=i;
           max=year_surive[i];
       }
      
    }
    return year_re;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24