代码求优化

Question

题目：给定一个整数数组，其中元素的取值范围为0到10000，求其中出现次数最多的数
思路：用一个一样大小的数组arr计数，然后找出arr的最大的那个有什么好算法吗？
//给定一个整数数组，其中元素的取值范围为0到10000，求其中出现次数最多的数public class Count{ public static void main(String args[]){
int array[] = {1,23,1,222,3,1,2,2,22,355,121,23,23,23,23,23,22,22,22,3,4};
int arr[] = new int[array.length];
for(int i = 0; i<arr.length;i++){
arr[i] = 0;
}
for(int i = 0; i<array.length;i++){
for(int j = i+1;j<array.length; j++){
if(array[i] == array[j]){
arr[j]++;
}
}
}
System.out.println("计数数组：");
for(int i = 0;i<arr.length;i++){
System.out.print(arr[i] + " ," );
}
int max = arr[0];
int index = 0;
for(int i =1; i<arr.length; i++){
if(arr[i]>=max){
max = arr[i];
index = i;
}
}
System.out.println(array[index]);

}
}

Answer 1

本帖最后由 AWUSOFT 于 2010-05-31 08:40:43 编辑

  

Answer 2

用map吧，遍历数组，如果map不存在这个数字，则作为key存进去，对应的value初始化为1，如果存在，则value加1，最后去找哪个value最大，输出key

Answer 3

先不说解决方案
楼主的代码很多冗余 还可以写精炼些
比如     for(int i = 0; i<arr.length;i++){
            arr[i] = 0;
        }
就不必要了 这里都已经给开空间了 赋的是 0 。
1楼的 hash 是个很不错的解决方案
还有就是  你已经知道了数组的取值范围[0, 10000]的
那就可以开一个长度为 10000 数组
遍历下输入的数组
给新开的数组赋值，
新开的数组 下标为输入数组的值
值为输入数组中的值出现的次数
最后遍历新开的数组就可以知道那个出现最多

Answer 4

for(int i = 0; i<array.length;i++){
            for(int j = i+1;j<array.length; j++){
                if(array[i] == array[j]){
                    arr[j]++;
                }
            }
        }for(int i = 0,j=i+1; i<array.length;i++)
{
   if(array[i] == array[j])
   arr[j]++;
   j++;
}

Answer 5

public static int findNumber(int [] array){
    TreeMap<Integer,Integer> cache = new TreeMap<Integer,Integer>();
    for(int num : array){
        Integer count = cache.get(num);
        if(count==null){
            count = new Integer(0);
        }
        count = count+1;
        cache.put(num,count);
    }
    return cache.lastKey();
}

Answer 6

public static int findNumber(int [] array){
    HashMap<Integer,Integer> cache = new HashMap<Integer,Integer>();
    for(int num : array){
        Integer count = cache.get(num);
        if(count==null){
            count = new Integer(0);
        }
        count = new Integer(count.intValue()+1);
        cache.put(num,count);
    }
    int maxEntryKey = 0;
    int maxKeyCount = 0;
    for(Map.Entry<Integer,Integer> e : cache.entrySet()){
        if(e.getValue()>maxKeyCount){
            maxKeyCount = e.getValue();
            maxEntryKey = e.getKey();
        }
    }
    return maxEntryKey;
}

Answer 7

int[] count = new int[10001];
int array[] = {1,23,1,222,3,1,2,2,22,355,121,23,23,23,23,23,22,22,22,3,4}; long start = System.nanoTime();
for(int num : array){
count[num]++;
}

int max = -1;
int loc = -1;
for (int i = 0;i<count.length;i++) {
if (max < count[i]) {
loc = i;
max = count[i];
}
}

System.out.println(loc);
long end = System.nanoTime();
System.out.println(end-start);耗时566919纳秒int array[] = {1,23,1,222,3,1,2,2,22,355,121,23,23,23,23,23,22,22,22,3,4};
long start2 = System.nanoTime();
int max2 = -1;
Map<Integer, Integer> map = new HashMap<Integer, Integer>();

for (int i : array) {
Integer count2 = map.get(i);
if (count2 == null) {
count2 = 1;
} else {
count2 = count2.intValue() + 1;
}
if (max2 < count2) {
max2 = i;
}
map.put(i, count2);
}

System.out.println(max2);
long end2 = System.nanoTime();
System.out.println(end2-start2);耗时802594纳秒不用hashMap快。

Answer 8

大家用hashMap好像最后都又遍历了一次啊，其实每次取出来的时候，保存比较一下就可以了。

Answer 9

public static void main(String[] args) {
int array1[] = { 1, 23, 1, 222, 3, 1, 2, 2, 22, 355, 121, 23, 23, 23,
23, 23, 22, 22, 22, 3, 4 };
int count = 0;
long start = System.nanoTime();
for (int i = 0; i < array1.length; i++) {
int tempCount = 0;
for (int j = 0; j < array1.length; j++) {
if (array1[j] == array1[i]) {
tempCount++;
}
}
if (tempCount > count) {
count = tempCount;
}
}
System.out.println(count);
long end = System.nanoTime();
System.out.println(end - start);
}6
588316

Answer 10

谢谢大家，对我很有帮助，O(∩_∩)O~有个小问题，为什么这么多人都想到用HashMap实现？HashMap有什么好处吗？

Answer 11

大侠，这代码写的太精髓了。。看不懂loc那个变量怎么是23？

Answer 12

声明了count=new int[10001];
是反过来做的,array中每一个数,与count中都有一个下标与之对应的元素,比如说222,在array中是一个元素中,在count中就是一个下标了,array中每出现一个数,就让count对应的位置上加+.如果出现了多次,每次就+1,这样最后每个位置上的值就是array中的出现的次数.有一个222就让count[222]++;出现一次就是count[222]=1;表示222出现了一次.
他的办法不足之外就是:如果最多次数有两个是相同的话,只能是第一次找到的那个