水贴王问题
个人信息:就读于燕大本科软件工程专业 目前大三;
本人博客: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 (此时是错误的)所以我们需要严格检查给出的数据是否符合题目模型,然后再去做出选择。
这个时候问题有转变成了 检查一个数组是否有数目过半的元素。
答案下篇给出,谢谢
原文:http://blog.csdn.net/cqs_experiment/article/details/25463511