HackerRank候鸟迁徙题Java代码优化 降低执行时长咨询

核心问题定位 #

你误以为第一阶段效率尚可，这是错误的，第一阶段才是引发超时的核心原因：

• 你在遍历arr的循环里调用Collections.frequency(arr, element)，这个方法每次都会完整遍历整个arr统计次数，时间复杂度直接达到O(n²)，当测试用例的arr长度达到1e5甚至更高时，必然超时。
• 而且你对同一个元素会重复统计多次，比如arr里有1000个1，你每次遇到1都会重新统计一次1的频次，完全是无效计算。

第一阶段优化方案 #

统计频次完全不需要每次全量遍历，单次遍历即可完成统计，时间复杂度降到O(n)：

• 题目明确候鸟的类型只有1、2、3、4、5共5种，甚至不需要用Map，直接用长度为6的数组（下标对应鸟类型，值对应频次）统计即可，比TreeMap的插入效率高得多。
• 如果你一定要用Map，也应该是遍历arr的时候，每次把对应key的计数+1，而不是每次调用frequency重新统计。

第二、第三阶段优化方案 #

你原来的2、3阶段也有冗余操作，可以直接省去额外的收集、排序步骤：

• 因为你要的是「频次最高的前提下，编号最小的鸟类型」，只需要从1到5从小到大遍历频次，记录第一个遇到的频次最高的编号即可，不需要收集所有符合条件的key再排序。
• 甚至可以在统计频次的同时就维护当前的最高频次和对应的最小编号，一次遍历直接出结果。

优化后代码示例 #

class Result {
    public static int migratoryBirds(List<Integer> arr) {
        // 鸟类型只有1-5，用数组统计频次，下标0空置不用
        int[] count = new int[6];
        for (int bird : arr) {
            count[bird]++;
        }
        int maxCount = 0;
        int result = 0;
        // 从小到大遍历，相同频次下先出现的就是编号更小的，直接覆盖即可
        for (int i = 1; i <= 5; i++) {
            if (count[i] > maxCount) {
                maxCount = count[i];
                result = i;
            }
        }
        return result;
    }
}

该版本时间复杂度为O(n)，空间复杂度为O(1)，可通过所有大输入测试用例。

内容的提问来源于stack exchange，提问作者htamayo