Java计数器操作代码正确性通过但性能仅40%，求优化建议

性能瓶颈 #

• 原代码每次遇到大于N的操作时，会执行两次O(N)级别的数组遍历：第一次调用getMax求数组最大值，第二次遍历全量更新所有计数器值
• 当数组A中存在大量全局更新操作时，整体时间复杂度会达到O(M*N)（M为A的长度，N为计数器数量），大流量场景下性能会严重下降

优化方案 #

核心思路是延迟更新，用全局基准值代替每次全量赋值操作，避免无意义的重复遍历：

1. 新增两个辅助变量：
   • base：存储全局更新的基准值，触发全局更新时直接把base设为当前最大值即可，无需修改计数器数组
   • currentMax：实时记录当前计数器的最大值，避免每次求最大值都遍历数组
2. 给指定下标计数器自增时，先判断该计数器当前值是否低于base，如果低于就先拉平到base再自增，同步更新currentMax
3. 所有操作执行完成后，统一遍历一次计数器数组，把所有低于base的元素设置为base，得到最终结果

优化后代码 #

package com.sample;

public class ConsecOperations {
    
    public int[] executeAll(int N, int[] A) {
        int[] counters = new int[N];
        int base = 0;
        int currentMax = 0;
        
        for (int value : A) {
            if (value > N) {
                // 全局更新操作仅修改基准值，O(1)复杂度
                base = currentMax;
            } else {
                int index = value - 1;
                // 先拉平到基准值再自增
                if (counters[index] < base) {
                    counters[index] = base;
                }
                counters[index]++;
                // 更新当前最大值
                if (counters[index] > currentMax) {
                    currentMax = counters[index];
                }
            }
        }
        
        // 最后统一补全基准值，仅遍历一次数组
        for (int i = 0; i < N; i++) {
            if (counters[i] < base) {
                counters[i] = base;
            }
        }
        
        return counters;
    }
    
    public static void main(String[] args) {
        ConsecOperations c = new ConsecOperations();
        int[] intArray = {3,4,4,6,1,4,4};
        int[] result = c.executeAll(5, intArray);
        for(int z : result) {
            System.out.print(z + ",\t");
        }
    }
}

优化效果 #

优化后整体时间复杂度稳定为O(M+N)，不管存在多少次全局更新操作，都只会遍历数组A一次、遍历计数器数组一次，性能可以达到满分标准。

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