水贴王问题
个人信息：就读于燕大本科软件project专业 眼下大三;
本人博客：google搜索“cqs_2012”就可以;
个人爱好：酷爱数据结构和算法，希望将来从事算法工作为人民作出自己的贡献;
博客内容：水贴王问题
博客时间：2014-5-7;
编程语言：Java ;
编程坏境：Windows 7 专业版 x64;
编程工具：jdk，eclipse x64;
制图工具：office 2010 ppt;
硬件信息：7G-3 笔记本;
真言
每一个人类似一台计算机，既高于计算机，又低于计算机，扬长避短，与时俱进。
题目水贴王问题（选自 编程之美）
有一个人发的帖子的数目超过了总帖子数目的一半，试求出这个人。
思路
数学建模：存在一堆发帖人，每一个人发帖人都一个id标识，然后找出这个发帖过半的id。（前提是已经存在这个发帖过半的id）
每一个用int标识，这些发帖人的id宛如一个数组的元素，试图找出数目过半的id号。
方法： 抵消法
既然有一个id号数目过半，那么它就是最多的，然而能够用它去抵消别的id号，一对一的去抵消，最后最多的还会剩下好多，这时候我们就知道答案了
个人算法设计例如以下（时间复杂度 O(n)， n为数组的长度）
static int _Find_more_than_half(int[] data) { int result = data[0] ; int number = 1; for(int i = 1;i < data.length;i++) { if( result == data[i] ) number++; else { number--; if(number == 0) { result = data [i] ; } } } return result; } 这个算法有缺陷，就是假设不存在发帖过半的id，它会找出错误的答案；假设存在发帖过半的id，则它会给出正确的答案。对于eg： 数组
int[] data ={1,1,1,1,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,3,3,3,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,4,4,44,4}; 它会给出 2 （此时是正确的）对于eg： 数组
int[] data ={1,1,2,2}; 他会给出 2 （此时是错误的）所以我们须要严格检查给出的数据是否符合题目模型，然后再去做出选择。
这个时候问题有转变成了 检查一个数组是否有数目过半的元素。
答案下篇给出，谢谢
转载于:https://www.cnblogs.com/bhlsheji/p/4212962.html
相关资源：数据结构—成绩单生成器