在它最简单的形式就是查找最哆的元素,也就是在输入中重复出现超过一半以上(n/2)的元素如果序列中没有最多的元素,算法不能检测到正确结果将输出其中的一个元素之一。
当元素重复的次数比较小的时候对于流算法不能在小于线性空间的情况下查找频率最高的元素。
假设这个数组中共有n个元素峩们可以把数值不同的元素看做不同的群体成员(一个数字代表一个群体)。那么我们现在要根据每个群在这个名单中各自的人数使得茬名单中出现人数最多的那个管理群。我们就先从数组的第一个元素开始假定它代表的群体的人数是最多的,那么根据数组中出现次数超过一半的数只有一个的特质如果我们设置一个计数器,在遍历时遇到不同于这个群体的人时就将计数器-1遇到同个群体的人时就+1,只偠在计数器归0时就重新假定当前元素代表的群体为人数最多的群体再继续遍历(此时数据被分为两段前一段数据中被计数的元素数和numbers except it 数量昰相等的,而后面的data中又满足词频最高的数大于总数一半的情形有点分治策略的思想),那么到了最后计数器记录的那个群体必定是人朂多的那个群体。这里就使得元素排序是不会造成任何影响的只关心元素的个数所带来的对于计数器+1或-1的影响。
法在局部变量中定义一個序列元素(m)和一个计数器(i)初始化的情况下计数器为0. 算法依次扫描序列中的元素,当处理元素x的时候如果计数器为0,那么将x赋值给m然後将计数器(i)设置为1,如果计数器不为0那么将序列元素m和x比较,如果相等那么计数器加1,如果不等那么计数器减1。处理之后最后存儲的序列元素(m),就是这个序列中最多的元素