数据频率有关问题
数据频率问题
如何在线性时间内判断一个整型数组中是否存在某一个数出现的次数大于等于数组元素总数的一半？
------解决方案--------------------
主元素问题，参考下帖：
http://community.****.net/Expert/topic/5589/5589029.xml?temp=.7094995
------解决方案--------------------
下面是检测超过总数一半的算法，与楼主的题目不一样。
两遍扫描
第一遍找出现次数最多的一个数，算法如下
变量V记录数值，变量C记录次数。
初值C = 0;
循环：如果C=0, 取一个数放到V；否则, 取一个数与V比较，如果相同，则C加1，如果不同，则C减1
直接没有下一个数，循环结束
如果C=0, 没有超过一半的；否则，扫描一遍，数一数V值的出现次数，看看是否超过半数。
时间复杂度 O(N)
如何在线性时间内判断一个整型数组中是否存在某一个数出现的次数大于等于数组元素总数的一半？
------解决方案--------------------
主元素问题，参考下帖：
http://community.****.net/Expert/topic/5589/5589029.xml?temp=.7094995
------解决方案--------------------
下面是检测超过总数一半的算法，与楼主的题目不一样。
两遍扫描
第一遍找出现次数最多的一个数，算法如下
变量V记录数值，变量C记录次数。
初值C = 0;
循环：如果C=0, 取一个数放到V；否则, 取一个数与V比较，如果相同，则C加1，如果不同，则C减1
直接没有下一个数，循环结束
如果C=0, 没有超过一半的；否则，扫描一遍，数一数V值的出现次数，看看是否超过半数。
时间复杂度 O(N)