leetcode - 5750 .人口最多的年份
主题说明：
给你二维整数数组logs。 每个logs[i]=[birthi，deathi]都表示第I个人的生日和死亡年。
年x的人口被定义为这一年中活着的人数。 第I个人计为年x的人口必须满足x在闭区间[birthi，deathi - 1]内。 请注意。 人不应该计入他们死亡那一年的人口。
回到人口最多、最早的一年。
这是今天leetcode第240次周赛的easy问题，早上周赛写的时候用暴力解决了。
思路如下：
首先，在映射中每年存储健在人数，然后根据映射中的值按降序排序，如果值相等，则根据key按升序排序。 (当然，也可以直接用数组保存。 那样更容易)。
以下是比赛中写的代码：
publicintmaximumpopulation (int [ ] logs ) {MapInteger，Integer map=new HashMapInteger，Integer； for(intI=0； i logs.length； I () /年生存人数int birth=logs[i][0]； int death=logs[i][1]； for(intj=Birth； j death； j () if (！ map.containskey(j ) ) map.put ) j，1 )； }else{map.put(j，map.get(j ) j ) 1； 对于}//map，按value降序排列ListMap.EntryInteger，integer list=newarraylistmap.entry integer，integer(map.entryset ) )； 在map.entrySet (为listcollections.sort ) list，new ComparatorMap.EntryInteger，Integer ) @overridepublicintcontect中=o1.getValue () ({return o2.getValue ) )- o1.getValue )； (//)2)进而return o1.getKey )- o2.getKey ) )按年份的升序排序； }； )； returnlist.get(0).getKey )； }这个问题的数据很弱，所以早上的周比赛这样写已经过去了。 但是，一旦数据给的很多，并且 [birth, death) 区间跨度很大，这样频繁对数组中进行区间修改操作的话，很大可能是会 TLE 的
随后，周赛结束后，看了xqdbbdalao发送的问题的解答，发现在差分数组上解决问题更好。
差分配列推荐看这个博客。 什么是差分配列？
差分数组简介：
差分配列(标记为minus )定义以下：
minus[0]=arr[0]； minus[i]=arr[i] - arr[i - 1]； (i 0)利用差分配序列容易地对原始序列(标记为arr )进行区间修改操作。 如果对数组arr的[left，right]的元素一律加/减d，则无需从left遍历到right，只需对[left，right]的各个元素分别加/减d即可，为http://www.sing
minus[left] =d； minus[right 1] -=d； //左闭右闭区间采用差分配序列对http://www.Sina.com//http://www.Sina.com/差分配序列http://www.Sina.com/序列进行http://www.Sina.com /操作
如果根据差异分配列查询原始数组(标记为arr )中的第index个元素arr[index]，则minus必须从i=0遍历到i=index。 arr[0]=minus[0]； arr[i]=minus[i] arr[i - 1]； (i 0)利用差分配列http://www.Sina.com/http://www.Sina.com/)频繁进行区间批量修改(相同常数d的加或减)操作，但稀疏查询。
xqdbbdalao提供的差分配列解法如下：
publicintmaximumpopulation (int [ ] [ logs ] ) {int[] minus=new int[100]； //差分配列： MINUS [ I ]=arr [ I ]-arr [ I-1 ]/MINUS [0]=arr [0] for (inti=0； i logs.length； I ) {minus[logs[i][0] - 1950]； minus[logs[i][1] - 1950]--； //不使用左闭右开区间[birth，death，1}int index=0； for(intI=1； i minus.length； I )//根据差分配序列minus求出原始序列arr的值，但在此不重新制作arr，而minus[i] =minus[i - 1]； if(Minus[I]Minus[index] ) {index=i； } }返回索引1950； } 修改差分数组:面试问题16.10 .幸存者人数
这个问题基本上和5750 .人口最多的一年一模一样。
代码如下。
//t 5750 publicintmaxaliveyear (int [ ] birth，int[] death ) ) {int[] minus=new int[102]； //差分配列： MINUS [ I ]=arr [ I ]-arr [ I-1 ] for (inti=0； i birth.length； I({Minus[Birth[I]-1900]； minus[death[i] - 1900 1]--； //左闭右闭区间[birth[i]，death[i]]}int index=0； for(intI=1； i minus.length； I({Minus[I]=Minus[I-1]； if(Minus[I]Minus[index] ) {index=i； } }返回索引1900； }