求教一个算法题

Question

请问如何找出一个整型数组里重复次数最多的三个数？（要考虑次数相同的情况）谢谢！

Answer 1

先放到数据库里,然后:
select ID, count(ID) from TABLE order by count(ID) desc limit 0, 3;

Answer 2

把整型数组里的整数作为key放入哈希中，value=整数的个数。
插补进哈希的value加加

Answer 3

先排序，然后从前往后挨个数，始终保留当前最多的三个数（含重复）。
或者用commons-collections里的Bag数据结构，一堆数字丢进去，数一下每个数字出现了几个，找最多三个（和2楼思想差不多）。

Answer 4

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.TreeMap;
import java.util.Map.Entry;public class Test {
public static void main(String args[]) {
TreeMap<Integer, Integer> map = new TreeMap<Integer, Integer>(); int[] array = new int[] { 1, 2, 3, 2, 1, 2, 3, 4, 5, 6, 8, 5, 4, 5, 6,
9, 8, 2, 6, 5, 4 };
for (int a : array) {
if (!map.containsKey(a))
map.put(a, 0);
map.put(a, map.get(a) + 1);
}

//根据次数进行排序
TreeMap<Integer, ArrayList<Integer>> sortMap = new TreeMap<Integer, ArrayList<Integer>>(new Comparator<Integer>(){
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}

});
for(Entry<Integer,Integer> e: map.entrySet()){
if( !sortMap.containsKey(e.getValue()))
{
sortMap.put(e.getValue(), new ArrayList<Integer>());
}
sortMap.get(e.getValue()).add(e.getKey());
}

int count = 3;
for(Entry<Integer,ArrayList<Integer>> e: sortMap.entrySet()){
List<Integer> list = e.getValue();
for (Integer i : list) {
if (count-- <= 0)
break;
System.out.println(i);
}


}

}


}

Answer 5

谢谢楼上的大哥给的精妙算法，不过不太看得懂^_^!主要是这段
 TreeMap<Integer, ArrayList<Integer>> sortMap = new TreeMap<Integer, ArrayList<Integer>>(new Comparator<Integer>(){
            @Override
            public int compare(Integer o1, Integer o2) {                
                return o2 - o1;
            }
            
        });

Answer 6

 如果不用到list,只用数组能够做吗，就是不用那些集合之类的用纯算法。

Answer 7

典型的hashmap使用题，到处都是

Answer 8

hashmap做起来最方便的，纯数组不是不行，麻烦

Answer 9

如果只用数组做比较，需要确保你要测试的数组中的值的个数是有限的，
比如你要测试数组a，它可能的值的个数N，然后新开一个数组b，长度为N，b[0]代表第一个可能的值的个数，b[1]代表第2个...b[N-1]是最后一个可能值的个数。
先遍历a，根据a[i]的值，将对应的b[x]值加1.
最后，获取b中数值最大的3个值所在的位置，即a中个数最多的3个值