题目难度: 中等
今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~
题目描述
给定 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]
题目思考
- 如何做到线性时间复杂度?
解决方案
思路
- 分析题目, 一个很容易想到的思路就是暴力法, 外层遍历 1900 到 2000 的每个年份, 然后内层遍历每个人, 统计当前年份仍然生存的人数
- 但这种方法效率很低, 时间复杂度达到了 O(N*Y) (N 是总人数, Y 是总年份), 有没有更高效的方法呢?
- 重新思考问题, 针对每个人的出生时间 b 和死亡时间 d, 其本质就是将年份区间
[b,d]的生存人数增加 1, 更新完所有年份区间后, 我们只需要从小到大遍历年份, 即可快速得到当前年份的生存人数了 - 但是, 直接更新区间的时间复杂度是 O(Y), 如何优化这部分呢?
- 这里我们就可以使用差分数组+前缀和的思路
- 差分数组统计当前年份与前一年份的生存人数之差, 即
diff[y]=people[y]-people[y-1], 注意由于年份 0 没有前一年份, 所以diff[0]=people[0] - 而如何求当前年份 y 的生存人数呢? 由于
diff[y]=people[y]-people[y-1], 我们只需要累加 0~y 的所有 diff, 即可得到people[y]
- 差分数组统计当前年份与前一年份的生存人数之差, 即
- 这样一来, 更新
[b,d]区间就只需要更新两个端点了, 因为相当于年份 b 增加了一个生存人数, 而年份 d+1 减少了一个生存人数, 即diff[b]++, diff[d+1]--, 将更新区间的时间复杂度降为 O(1) - 另外注意题目的年份范围在 1900
2000 之间, 所以我们无需存储 02000 所有年份, 而是可以将年份减去 1900, 这样只需要存储 0~100 即可, 进一步优化了空间消耗 - 下面代码就对应了上面的整个过程, 且每一步有详细的注释, 方便大家理解
复杂度
- 时间复杂度
O(N+Y): 只需要遍历一遍 N (总人数, 110000), 再遍历一遍 Y (总年份, 19002000) - 空间复杂度
O(Y): 只需要存储所有年份的差分数组
代码
class Solution:
def maxAliveYear(self, birth: List[int], death: List[int]) -> int:
# 差分数组+下标转换
n = len(birth)
# diff是差分数组, 统计区间两个端点的变化情况
# 注意diff下标最大可以到101(对应死亡时间2000年的情况), 所以这里数组上限是102
diff = [0] * 102
for i in range(n):
# 出生年份的人数加1
# 这里将年份减去1900, 转成0~100的值, 减少空间消耗
diff[birth[i] - 1900] += 1
# 死亡+1年份的人数减1
diff[death[i] + 1 - 1900] -= 1
sm = 0
mx, res = 0, 0
for i, x in enumerate(diff):
# sm是前缀和, 即为当前年份的生存人数
sm += x
if sm > mx:
mx = sm
# 注意转换成原始年份
res = i + 1900
return res
大家可以在下面这些地方找到我~😊
我的公众号: 算法精选, 欢迎大家扫码关注~😊
京公网安备 11010502036488号