转自：http://blog.chinaunix.net/uid-627012-id-2706170.html
众数算法a) 问题 在一个由元素组成的表中，出现次数最多的元素称为众数。试写一个寻找众数的算法,并分析其计算复杂性。
众数算法
a) 问题 在一个由元素组成的表中，出现次数最多的元素称为众数。试写一个寻找众数的算法,并分析其计算复杂性。 b) 分析 对于这个问题，比较容易的是使用排序的算法，对元素表进行排序，然后统计元素出现的个数，得出众数。则这个问题的平均时间复杂度取决于排序算法。 对于n个分布在m1~m2的整数元素，我们可以用一个数组来索引这些元素出现的个数。这样的话，对n个原始数据遍历，然后再遍历计数数组，复杂度为O( n + m ) = O ( n )。 显然，如果 |太大的话，对空间的要求会非常大。所以综合两种算法。 当 的时候，我们采用索引数组的办法。 其他情况采用排序的算法。
c) 编程实现
众数算法:/** 在一个元素组成的表中，出现次数最多的元素称为众数 * 试写一个寻找众数的算法,并分析其计算复杂性。 */ public class MostNumber { final static int maxNumber = 100; /** 程序入口 */ public static void main(String args[]) { int a[] = new int[100]; int m1=0, m2=0; //初始化数组 for(int i=0; i<100; i++) { a[i] = Math.round((long)(Math.random()*100)); System.out.print(" "+a[i]); if(i%5==4) { System.out.print(" "); } } System.out.println(""); //取最小值 for(int i=0; i<100; i++) { if(a[i]<m1) { m1=a[i]; } } //取最大值 for(int i=0; i<100; i++) { if(a[i]>m2) { m2=a[i]; } } //编码核心部分； if( (m2-m1) <maxnumber &&="" ((m2-m1)="" 100)<1000) { int m[] = new int[maxNumber]; //索引数组 for(int i=0; i<100; i++) { m[a[i]-m1]++; } //求众数 int maxCount=0, index = 0; for(int i=0; i<maxnumber; i++) { if(m[i]>maxCount) { maxCount=m[i]; index = i; } } System.out.println("方法1：结果"); for(int i=0;i<100;i++) { System.out.println("Num:"+(i+m1)+" "+m[i]); } System.out.println("方法1：众数为 "+(index+m1)); }
