给定元素取值1~1e5的大规模整数列表，如何优化O(n²)的整除计数逻辑

优化核心思路 #

• 原实现采用双重循环遍历匹配，时间复杂度为O(n²)，当输入规模为1e5时运算量会达到1e10级别，完全无法在可接受时间内完成。
• 结合题目给出的“输入元素取值范围固定在1~1e5”的约束，我们可以通过频次统计+倍数筛法将时间复杂度降低到O(n + M log M)（其中M为输入列表的元素最大值，题目中M最大为1e5），完全适配大规模输入的性能要求。
• 优化的本质是把“对每个目标元素，遍历整个列表找能整除它的数”的正向枚举，反向调整为“对列表中出现的每个数，找到所有能被它整除的目标元素并累加计数”，借助埃氏筛的思想消除重复遍历，没有任何多余计算。

具体实现流程 #

• 第一阶段：遍历原列表，记录所有元素的最大值maxVal，同时统计每个数值的出现频次，存入数组freq。这一步的时间复杂度为O(n)。
• 第二阶段：初始化计数数组cnt，cnt[x]的含义为原列表中可以整除x的元素总个数。随后从1到maxVal依次枚举每个可能的约数d，遍历d的所有整数倍数m（取值为d、2d、3d……直到不超过maxVal），将freq[d]累加到cnt[m]上。这一步的总运算量为调和级数求和：M*(1 + 1/2 + 1/3 + ... +1/M) ≈ M*lnM，当M=1e5时总运算量仅约120万次，性能开销极低。
• 第三阶段：按照原列表的顺序遍历每个元素e，直接输出预先计算好的cnt[e]作为结果，保证和原代码的输出顺序、计算结果完全一致。这一步的时间复杂度为O(n)。

正确性校验（对照给定样例） #

针对样例输入2, 4, 8, 2：

1. 频次统计结果：freq[2] = 2、freq[4] = 1、freq[8] = 1，其余数值对应的频次为0。
2. 筛法计数过程：
   • 约数2的频次为2，为所有2的倍数的计数加2：cnt[2] += 2、cnt[4] +=2、cnt[8] +=2
   • 约数4的频次为1，为所有4的倍数的计数加1：cnt[4] +=1、cnt[8] +=1
   • 约数8的频次为1，为所有8的倍数的计数加1：cnt[8] +=1
3. 最终预计算的计数结果为cnt[2] = 2、cnt[4] =3、cnt[8] =4，和原代码的输出完全匹配。

优化后的Java代码 #

public static void countDivibilies(List<Integer> list) {
    // 统计列表中的最大值，确定数组长度上限
    int maxVal = 0;
    for (int num : list) {
        maxVal = Math.max(maxVal, num);
    }
    // 统计每个数值在原列表中的出现频次
    int[] freq = new int[maxVal + 1];
    for (int num : list) {
        freq[num]++;
    }
    // 筛法预计算每个数对应的可整除元素总个数
    int[] cnt = new int[maxVal + 1];
    for (int d = 1; d <= maxVal; d++) {
        // 遍历约数d的所有倍数
        for (int m = d; m <= maxVal; m += d) {
            cnt[m] += freq[d];
        }
    }
    // 按原列表顺序输出结果，与原逻辑完全对齐
    for (int e : list) {
        System.out.println(e + " : " + cnt[e]);
    }
}

性能对比 #

• 原代码的O(n²)复杂度在n=1e5时需要约1e10次循环运算，运行时间会达到小时级别，完全无法满足生产要求。
• 优化后的代码总复杂度为O(n + M log M)，当n=1e5、M=1e5时总运算量约130万次，运行时间仅需毫秒级，内存占用仅约800KB（两个长度为1e5的int数组），完全满足性能与资源约束。

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