使用Java Hashtable处理HackerRank大输入时结果错误求助

看起来你在HackerRank的Migratory Birds问题上卡壳了——前四个测试用例都顺利通过，结果到了最大规模的测试用例就返回错误答案。别担心，这种情况大概率是细节逻辑没覆盖到，咱们一步步来排查。

首先，先补全你没写完的代码片段（毕竟你写到birds.get(ar[i])==nu...就断了），我猜你的核心计数逻辑大概是这样的：

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {
    static int migratoryBirds(int n, int[] ar) {
        Hashtable<Integer,Integer> birds = new Hashtable<Integer,Integer>();
        for (int i=0;i<n;i++) {
            if (birds.get(ar[i])==null) {
                birds.put(ar[i], 1);
            } else {
                birds.put(ar[i], birds.get(ar[i]) + 1);
            }
        }
        // 这里应该是找出现次数最多的鸟，但逻辑可能有漏洞
        int maxCount = 0;
        int result = 0;
        for (Map.Entry<Integer, Integer> entry : birds.entrySet()) {
            if (entry.getValue() > maxCount) {
                maxCount = entry.getValue();
                result = entry.getKey();
            }
            // 这里是不是没处理「计数相同选编号最小的鸟」的情况？
        }
        return result;
    }
}

问题出在哪？ #

前四个小测试用例通过，说明你的基础计数逻辑是对的。出错的核心原因几乎可以确定是题目要求的「多个鸟类出现次数相同时，返回编号最小的那个」你没处理，再加上Hashtable的遍历顺序不保证按key升序，导致大规模测试用例里恰好出现多鸟同频的场景时，你返回了更大的编号。

修正后的完整代码 #

我帮你把逻辑补全，同时优化了写法：

import java.io.*;
import java.util.*;

public class Solution {
    static int migratoryBirds(int n, int[] ar) {
        Hashtable<Integer, Integer> birdCount = new Hashtable<>();
        
        // 用getOrDefault简化计数逻辑，不用写if-else判断null
        for (int birdId : ar) {
            birdCount.put(birdId, birdCount.getOrDefault(birdId, 0) + 1);
        }
        
        int maxFrequency = 0;
        int smallestBirdId = Integer.MAX_VALUE;
        
        // 遍历所有统计结果，同时处理同频选小编号的情况
        for (Map.Entry<Integer, Integer> entry : birdCount.entrySet()) {
            int currentId = entry.getKey();
            int currentCount = entry.getValue();
            
            // 情况1：当前鸟的数量比之前的最大值大，直接更新
            if (currentCount > maxFrequency) {
                maxFrequency = currentCount;
                smallestBirdId = currentId;
            } 
            // 情况2：数量和最大值相同，选编号更小的那个
            else if (currentCount == maxFrequency) {
                if (currentId < smallestBirdId) {
                    smallestBirdId = currentId;
                }
            }
        }
        
        return smallestBirdId;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int n = Integer.parseInt(bufferedReader.readLine().trim());

        int[] ar = new int[n];
        String[] arItems = bufferedReader.readLine().trim().split(" ");

        for (int i = 0; i < n; i++) {
            ar[i] = Integer.parseInt(arItems[i]);
        }

        int result = migratoryBirds(n, ar);

        bufferedWriter.write(String.valueOf(result));
        bufferedWriter.newLine();

        bufferedReader.close();
        bufferedWriter.close();
    }
}

更高效的替代方案 #

其实这个问题完全没必要用Hashtable——题目里明确说了鸟类的编号是1到5，直接用数组统计效率更高，还能避免哈希表遍历顺序的问题：

static int migratoryBirds(int n, int[] ar) {
    int[] counts = new int[6]; // 索引0闲置，1-5对应鸟的编号
    for (int id : ar) {
        counts[id]++;
    }
    
    int maxCount = 0;
    int resultId = 0;
    // 从1到5遍历，天然保证同频时选小编号
    for (int i = 1; i <= 5; i++) {
        if (counts[i] > maxCount) {
            maxCount = counts[i];
            resultId = i;
        }
    }
    return resultId;
}

这个写法简单直接，绝对能通过所有测试用例。

内容的提问来源于stack exchange，提问作者Juan Francisco Garcia