江湖中又现阿里的算法面试题目：找出数组中重复次数最多的元素并打印。我碰巧在《编程珠玑》中看到了，javaeye上的帖子的各种实现效率或多或少的有性能问题，更是有人好高骛远的讨论到mapreduce了，明显的把裝B的难度从“芙蓉姐姐”直接转到“小月月”。
涉及到重复元素的问题，在线性时间排序算法（Linear-Time Sorting）中到计数排序（Counting Sorting）或许是解决这个问题的。简单介绍下计数排序：
计数排序算法的时间复杂度是O(k) + O(n) + O(k) + O(n) = O(k + n)，在数组中的元素重复较少的时候，和快速排序比起来效率较低。 这个题目只是求出B[j]的最大值，最后一步遍历B[k]都可以省去，在遍历A[n]的时候可以直接记录就可以了。
具体算法的java实现如下：
package com.longtask.algorithms;
import java.util.Arrays;
import java.util.Random;
public class CountingSort {
private static final int N= 10000;
private static final int K= 1000;
/**
* 得到计数数组
* @param num
* @return
*/
public static int[] computeCountingNum(int[] num){
int maxAppearNum = 0;
int count = 0;
int[] countingNum = new int[K];
int value,countTmpValue;
for(int i=0;i
value = num[i];
countTmpValue = countingNum[value];
//查找出现次数最多的数字
if(countTmpValue > count){
count = countTmpValue;
maxAppearNum = value;
}
countingNum[value] = countingNum[value] + 1;
}
//打印出满足阿里面试要求到数据
System.out.println("\n"+maxAppearNum);
System.out.println(count);
return countingNum;
}
/**
* 遍历计数数组，得到排序结果
* @param num
* @return
*/
public static int[] sortedNum(int[] num){
int[] countingNum = computeCountingNum(num);
int[] sortedNum = new int[N];
int value;
int j = 0;
for(int i=0;i
value = countingNum[i];
if(value > 0){
while(value > 0){
sortedNum[j] = i;
--value;
++j;
}
}
}
return sortedNum;
}
/**
* 产生随机数
* @return
*/
public static int[] randomNumber(){
int[] num = new int[N];
Random random = new Random();
for(int i=0;i
int m = random.nextInt(K);
num[i] = m;
}
return num;
}
public static void main(String[] args) {
int[] num = CountingSort.randomNumber();
//计数排序耗时
long t1 = System.currentTimeMillis();
CountingSort.sortedNum(num);
long t2 = System.currentTimeMillis();
System.out.print(t2-t1);
System.out.println();
//快速排序耗时
long t3 = System.currentTimeMillis();
Arrays.sort(num);
long t4 = System.currentTimeMillis();
System.out.print(t4-t3);
}
}
最后测试了下快速排序和技术排序在重复数值较多的情况下的效率，明显技术排序更加靠谱。不同的场景选择不同的算法。
线性时间排序算法（Linear-Time Sorting）合计有3种算法，如果你对文字感兴趣点击这里
当然，一边喝点酒，一边听课是不是更爽，看这段视频吧！