1

如果该数字出现在数组大小的一半以上，则此方法返回正整数数组中的数字，否则返回 -1。我需要为更大的数组改进它的运行时间(10^5<size<10^8)。有什么建议么？

public static int findResult(int arr[],int len){

    int val=0;
    HashMap<Integer,Integer> map=new HashMap<Integer,Integer>();
    for(int i=0;i<len;i++){
        if(map.containsKey(arr[i])){
            val = (Integer)map.get(arr[i]);
            map.put(arr[i], val+1);
        }else{
            val=1; 
            map.put(arr[i], val);
        }
    }
    Iterator<Integer> it=map.keySet().iterator();
    while(it.hasNext()){
        int next=it.next();
        if((Integer)map.get(next)>(len/2)){
            return next;
        }
    }
    return -1;
}
4

4 回答 4

6

您可以在没有地图的情况下执行此操作，从而无需装箱/拆箱：

public static int findResult(int[] arr, int len) {
    if(len == 0) return -1;
    if(len == 1) return arr[0];

    int element = arr[0];
    int count = 1;
    for(int i = 1; i < len; i++) {
        if(arr[i] == element) {
            count++;
        } else if(count > 0) {
            count--;
        } else {
            element = arr[i];
            count = 1;
        }
    }

    count = 0;
    for(int a:arr) {
        if(a == element) {
            count++;
        }
    }

    return (count > len / 2) ? element : -1;
}
于 2013-05-05T12:44:16.233 回答
1

为什么不与输入哈希映射的每次迭代后的长度（您正在运行的第二个迭代器循环）进行比较？这是在 hashmap 完成的时候，你知道结果，你只需要这样做一次。

于 2013-05-05T12:25:45.860 回答
0

这个 IMO 更短更高效

public static int findResult(int arr[], int len) {
    HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
    for (int i = 0; i < len; i++) {
        Integer val = map.get(arr[i]);
        if (val != null) {
            map.put(arr[i], val + 1);
        } else {
            map.put(arr[i], 1);
        }
    }
    for (Entry<Integer, Integer> e : map.entrySet()) {
        if (e.getKey() > (len / 2)) {
            return e.getValue();
        }
    }
    return -1;
}

1) 原始版本在地图上使用 2 个方法调用

if(map.containsKey(arr[i])){
        val = (Integer)map.get(arr[i]);

我的使用一张 map.get

2）这个

 while(it.hasNext()){
        int next=it.next();
        if((Integer)map.get(next)>(len/2)){

在性能方面是如此糟糕，以至于即使 Sonar 或 FindBugs 也会立即检测到它并建议用我提供的替换

于 2013-05-05T12:28:22.797 回答
0

你可以使用一个临时变量来存储最大的量，每次你增加某个变量的计数器时，检查它是否比你的临时大，如果是，替换它，否则继续，这样你就可以在没有第二个循环，你只知道你的答案在 temp 变量中

于 2013-05-05T12:53:53.373 回答