美团笔试--小美的众数
比较有意思的题目,看了看别人的思路发现和我不太一样,记录一下
小美拿到一个数组。她希望你求出所有区间众数之和。
定义区间的众数为出现次数最多的那个数。如果有多个数出现次数最多,那么众数是其中最小的那个数。
n表示数组大小,200000范围
ai 取值为1或者2
输出一个正整数,代表所有区间的众数之和
示例
输入
3
2 1 2
输出
9
思路:
维护一个2*n+1的区间
这个区间的表示如下
我们只需要处理新增加的元素对应的新区间即可
比如处理第i个元素的时候,只需要关注[0,i],[1,i],[2,i].......[i,i]这些新增加的区间即可
因为知道这些新增加的区间其实就是上一个元素i-1对应的所有新区间后面添加一个元素a[i],以及添加一个由a[i]单独组成的区间
所以,我们可以从上一个新增区间的状态获取当前区间的状态,
即,当新元素为1的时候,就相当于1与2数量相同的区间数量对应的index向右边移动一次,为2时向左移动,并且添加对应的单独元素组成的区间,也就是在对应的元素+1
最后维护好1比2多的总区间数量以及2比1多的总区间数量即可
复杂度O(n)
public class s4 { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); // 记录数组,0~n-1部分从n-1下标开始记录1比2的数量多1,2,3,4.....个的区间数量 // 同理n+1~2n+1部分表示2比1多1,2,3,4....的区间数量 int[] vis = new int[ 2 * n + 1]; int[] a = new int[n]; for (int i = 0; i < n; i++) { a[i] = scanner.nextInt(); } long res = 0L; // 1与2数量相同的位置index int pos = n; // 1比2数量多的区间数量总和 int sum1 = 0; // 2比1数量多的区间数量总和 int sum2 = 0; // 每次只处理新增加的区间 for (int i = 0; i < n; i++) { if (a[i] == 1){ // 新增加一个空的区间 vis[pos]++; // 当前位置是1,所有区间都会加上一个1,所以。pos向左边移动一下 // 移动的时候维护好sum1和sum2 sum1 += vis[pos]; pos++; sum2 -= vis[pos]; }else{ vis[pos]++; sum2 += vis[pos]; pos--; sum1 -= vis[pos]; } // sum2全是众数为2的区间数量,sum1全是众数为1的数量 res += (sum2*2); res += sum1; // 1和2数量相同,认定1为众数 res += vis[pos]; } System.out.println(res); } }