人数"/>
【力扣】面试16.10 生存人数
题目描述
给定N个人的出生年份和死亡年份,第i个人的出生年份为birth[i],死亡年份为death[i],实现一个方法以计算生存人数最多的年份。
你可以假设所有人都出生于1900年至2000年(含1900和2000)之间。如果一个人在某一年的任意时期都处于生存状态,那么他们应该被纳入那一年的统计中。例如,生于1908年、死于1909年的人应当被列入1908年和1909年的计数。
如果有多个年份生存人数相同且均为最大值,输出其中最小的年份。
来源:力扣(LeetCode)
链接:
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
算法思路
FOOL
做5412. 在既定时间做作业的学生人数时想到的……
class Solution:def maxAliveYear(self, birth: List[int], death: List[int]) -> int:def he(y):return sum(1 for i,j in zip(birth,death) if i<=y<=j)MAX=0year=0for i in range(min(birth),max(death)+1):k=he(i)if k>MAX:MAX=kyear=ireturn year
执行用时 :784 ms, 在所有 Python3 提交中击败了12.61%的用户
内存消耗 :14.3 MB, 在所有 Python3 提交中击败了100.00%的用户
NAIVE
class Solution:def maxAliveYear(self, birth: List[int], death: List[int]) -> int:dp=[0]*101for i,j in zip(birth,death):for k in range(i-1900,j-1900+1):dp[k]+=1return dp.index(max(dp))+1900
执行用时 :312 ms, 在所有 Python3 提交中击败了43.70%的用户
内存消耗 :14.6 MB, 在所有 Python3 提交中击败了100.00%的用户
PERFECT | 前缀和
用两个数组保存从1900年到2000年间每年的出生人口和死亡人口,最大生存人数就是总的生成人口-总的死亡人口,唯一需要注意的是 应该是第i年的总出生人口-第i-1年的死亡人口,因为当年死亡的人仍算存活。
class Solution:def maxAliveYear(self, birth: List[int], death: List[int]) -> int:dic = collections.defaultdict(int)for c in birth:dic[c]+=1for c in death:dic[c+1]-=1maxn = 0cur =0res = -1for i in range(1900,2001):cur+=dic[i]if cur>maxn:res=imaxn = curreturn res
执行用时 :96 ms, 在所有 Python3 提交中击败了67.59%的用户
内存消耗 :14.5 MB, 在所有 Python3 提交中击败了100.00%的用户
更多推荐
【力扣】面试16.10 生存人数
发布评论