微软8月19笔试统计

比较有意思的题目，看了看别人的思路发现和我不太一样，记录一下小美拿到一个数组。她希望你求出所有区间众数之和。定义区间的众数为出现次数最多的那个数。如果有多个数出现次数最多，那么众数是其中最小的那个数。n表示数组大小，200000范围ai 取值为1或者2输出一个正整数，代表所有区间的众数之和示例输入32 1 2输出9思路：维护一个2*n+1的区间这个区间的表示如下我们只需要处理新增加的元素对应的新区间即可比如处理第i个元素的时候，只需要关注[0,i],[1,i],[2,i].......[i,i]这些新增加的区间即可因为知道这些新增加的区间其实就是上一个元素i-1对应的所有新区间后面添加一个元素...