数组中出现次数第k多的数字(求次数前k多的问题)

1.思路;先定义一个map<Integer,Integer>,key:数组元素,value;该元素出现的次数。
挨个添加进map中,求出每个元素对应的出现次数。
但有一个问题:map是无序的,如何对其value排序?
将map.entry放入list中,对每一个entry中的value排序。

List<`Entry<Integer,Integer>> list = new ArrayList<Entry <Integer,Integer>>(map.entrySet());
Collections.sort(list,new MapSort());
class MapSort implements Comparator<Map.Entry<Integer,Integer>>{

    @Override
    public int compare(Entry<Integer, Integer> o1, Entry<Integer, Integer> o2) {
        return o1.getValue()>o2.getValue()?o1.getValue():o2.getValue();
    }

}

具体实现代码:

package com.java.排序;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.TreeMap;

/** 
 * @author wangpei 
 * @version 创建时间:2017年5月15日 下午11:31:03 
 * 类说明 
 */
public class 数组中出现次数前k多的数字 {
    public static int get(int a[],int k){
        List<Map> s=new ArrayList<Map>();
        Map<Integer,Integer> map=new HashMap<Integer,Integer>();
        for(int i=0;i<a.length;i++){
            if(map.containsKey(a[i])){
                int count=map.get(a[i])+1;
                map.put(a[i], count);
            }
            else
                map.put(a[i], 1);
        }
        List<Entry<Integer,Integer>> list=new ArrayList<Entry<Integer,Integer>>(map.entrySet());
        Collections.sort(list,new MapCompare() ); 

     return list.get(k-1).getKey();



    }
    public static void main(String[] args) {
        int []a={11,1,1,1,1,2,2};
        System.out.println(get(a,3));

    }

}
class MapCompare implements Comparator<Map.Entry<Integer, Integer>>{

    @Override
    public int compare(Entry<Integer, Integer> o1, Entry<Integer, Integer> o2) {
        return o1.getValue()>o2.getValue()?o1.getValue():o2.getValue();
    }
}

补充:map对key排序时,可直接
使用TreeMap trp=new TreeMap<map>;
将其变为TreeMap格式。

原文地址:https://www.cnblogs.com/wangxiaopei/p/8551205.html