查询一个数组中字符出现最多频率的算法
因为觉得
这种复杂度非常的不科学... 所以我Google了一下, 然后在stackoverflow上找到了一个问题...algorithm - Find mode of a multiset in given time bound (most multiplicity)所以我想你要问的复杂度应该是
才对...那个算法基本是对的, 不过需要注意的是, 找到出现次数过半的元素会有点问题, 最好是不断划分, 使得长度最大的没有元素出现次数过半的一段的长度小于等于当前出现次数在某一段中过半且出现次数最多的元素出现的次数(妈呀好绕口). 然后, 每次把当前没有出现次数过半的元素, 并且最长的那一段拿来split. 然后对分出的两段分别考虑是否满足 1) 存在出现次数过半的元素 2)是否影响全局的答案.我来证明一下那个做法的复杂度...不过因为很多证明步骤可以直接从快排那里搬过来, 所以写的也比较简略了...(这里假设每次都把所有元素都划分过一次的最坏情况)首先, 整个算法最后的复杂度上界显然是
其中
是最后划分了多少次.而这时候, 感情上每段的长度应该是
, 要让这个长度小于等于
, 那也就是
两边取对数就是
, 但是我们并不需要这个长度小很多(恰好满足就够了), 所以取
.最后的复杂度大概就是 【查询一个数组中字符出现最多频率的算法】
.并没有证明的很严格..但是感情上大概就这样了...
推荐阅读
- 同比■同比增长7.1%！2021年的第一个节你花了多少钱？
- “他是我第一个会说普通话的老师”：一对师生折射青海山村蝶变
- 有必要重新开个C店吗
- 大学再有三个月就结束了，没学到知识，参加一个软件测试培训机构好吗
- 汽车|长安UNI-K又将开创一个新的"引力"纪元？
- 神话|武汉传奇父亲：一个平行班孩子创造的高考神话（感动上万家长）
- 王者荣耀李白能不能出肉
- 直播会成为品牌传播的另一个途径么有哪些可行的方法感觉有戏又没头绪好捉急。
- 怎样成为一名合格的Python程序员?
- 知乎有没有必要增加一个特别关注功能