search

wtysos11 / blogWiki

Use to store public paper and organize them.
17 stars 4 forks source link

绝对众数问题与摩尔投票算法 #237

Open wtysos11 opened 3 years ago

wtysos11 commented 3 years ago

绝对众数就是数量占总数一半的众数。这个是字节二面时的笔试题，当时想的方法是排序之后取中间值，算是比较简单的解法，结果因为好久没写C++还写错了（结果还是过了，然后在三面的时候挂掉了）

摩尔投票算法，思想是对抗抵消思想，时间复杂度为遍历一遍数组O(n)，空间复杂度为O(1)

进阶问题：区间摩尔投票问题，在线段树上应用摩尔投票