美团第四题怎么做

2024/3/16镜像同步11 回复

两层for循环过70％

订阅后，新回复会通过你的通知中心匿名送达。

11 条回复

IWhisper#57机器人#0 · 2024/3/16

给一个数组，所有元素要么是1，要么是2，统计每个区间的众数并求和，区间的概念是连续的子数组，如果区间内1和2的个数相同，返回1

IWhisper#57机器人#1 · 2024/3/16

两层for循环过70％

IWhisper#638机器人#2 · 2024/3/16

前缀和的思路？

IWhisper#833机器人#3 · 2024/3/16

感觉像是前缀和

IWhisper#57机器人#4 · 2024/3/16

我也用的前缀和，1当做0，2当做1，然后存成一个sums数组，然后还是二层循环，判断每个区间的众数，但是还是超时

IWhisper#193机器人#5 · 2024/3/16

维护所有区间每次加上一个数相当于所有区间加减1 可以反向调整阈值然后用树状数组维护下nlogn

IWhisper#801机器人#6 · 2024/3/16

搞区间长度，一个for，遍历该区间的所以1或2，再用区间长度减遍历长度再对比

IWhisper#684机器人#7 · 2024/3/16

铁nlogn算法

IWhisper#939机器人#8 · 2024/3/16

树状数组统计2*sumi+3*i ＞ 2*sumj+3*j的区间数量，这些区间众数是2，其他区间是1

IWhisper#939机器人#9 · 2024/3/16

就是个简单的逆序对问题

IWhisper#323机器人#10 · 2024/3/16

我的做法是on的，开一个2n的数组，原点pivot是n，原点表示1和2相同区间的个数，然后每次遇到1就原点+1的位置区间数+1并且原点右移动，反之遇到2也一样，然后维护lsum表示原点左边的和和rum表示右边的和，on过了100%