一道阿里电话面试中的算法题

 public static void findRepeatMaxValue(int[] arr) {
		long time1 = System.nanoTime();
		HashMap<Integer, Integer> box = new HashMap<Integer, Integer>();
		int maxValue = 0;
		int maxCount = 0;
		for (int i = 0; i < arr.length; i++) {
			Integer count = box.get(arr[i]);
			box.put(arr[i], count == null ? 1 : ++count);
			int newCount = box.get(arr[i]);
			if(newCount > maxCount) {
				maxCount = newCount;
				maxValue = arr[i];
			}
		}
		long time2 = System.nanoTime();
		System.out.println("findRepeatMaxValue time is "
				+ ((time2 - time1) / 1000000.0) + "ms");
		System.out.println("maxValue : " + maxValue +"  maxCount : " + maxCount);
	}

 public static void main(String[] args) {
		Random rand = new Random();	
		int arr[] = new int[1000000];
		for (int i = 0; i < arr.length; i++) {
			arr[i] = rand.nextInt(100);
		}
		findRepeatMaxValue(arr);
	}

    public static void findRepeatMaxValue(int[] arr) {

       long time1 = System.nanoTime();

       int max = 0;

       // 定义MAP KEY表示存放的数字，VALUES表示出现的次数

       Map<Integer, Integer> map = new HashMap<Integer, Integer>();

       for (int n : arr) {

           if (map.containsKey(n)) {

              map.put(n, map.get(n) + 1);

           } else {

              map.put(n, 1);

           }

           // 比较是此数是否为最大次数

           if (map.get(n) > max)

              max = map.get(n);

       }

       for (Map.Entry<Integer, Integer> m : map.entrySet()) {

           if (m.getValue() == max) {

              System.out.println(m.getKey() + " 出现了 " + m.getValue() + " 次.");

           }

       }

       long time2 = System.nanoTime();

       System.out.println("findRepeatMaxValue time is "

              + ((time2 - time1) / 1000000.0) + "ms");

    }

    public static void main(String[] args) {

       Random rand = new Random();

       int arr[] = new int[1000000];

       for (int i = 0; i < arr.length; i++) {

           arr[i] = rand.nextInt(100);

       }

       findRepeatMaxValue(arr);

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<N;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<K;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<N;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);
	}
}

看了楼主的代码，想自己试试，结果发现你那第一种方法很明显是有错误的，更正后的代码如下：

		ArrayUtil.quickSort(arr, 0, arr.length - 1);
		
		int now = 1;
		int pre = 1;
		for(int i = 0; i < arr.length - 1; i ++) {
			if(arr[i] == arr[i + 1]) {
				now ++;
			} else {
				if(now >= pre) {
					pre = now;
				}
//now = 1;应该放在if语句的外面
				now = 1;
			}
		}
//缺少这一句
		if(now >= pre) {
			pre = now;
		}

public static void find3(int[] arr){
		HashMap<Integer,Integer> hm=new HashMap<Integer, Integer>();
		for(int i=0;i<arr.length;i++){
			if(hm.containsKey(arr[i])) {
				int count=hm.get(arr[i]);
				hm.put(arr[i], ++count);
			 
			}else{
				hm.put(arr[i],1);
			}
		}
		
		Iterator<Entry<Integer, Integer>> it=hm.entrySet().iterator();
		int pre=0;
		int max=arr[0];
		while(it.hasNext()) {
			Entry<Integer, Integer> en=it.next();
			int key=en.getKey();
			int val=en.getValue();
			if(val>pre){	
				pre=val;
				max=key;
			}
			
		}
		
		//System.out.println(max);
		
	}

补充一点,初始容量和装载因子是影响hash函数性能的重要因子,也就是影响你地址是否冲突的重要因素,当地址冲突时,选择合适的再散列函数,对相应元素进行地址分配,以便无冲突装载该元素,这个也是很重要的,