如何优化可整除度计算算法？附问题说明与现有Java实现代码

原代码存在的问题 #

• 时间复杂度过高：两层遍历keys，时间复杂度为O(n²)，当keys元素数量较多时（如超过1000）性能会急剧下降
• 数值计算错误：需求要求最大可整除度乘以10^5（100000），原代码中错误乘以了10000，返回结果不符合要求
• 不必要的重量级API使用：两个int乘积最大值不会超过2^62，用long类型即可存储，不需要使用BigInteger带来额外开销

优化思路 #

首先统计keys中所有正整数的出现频率，过滤掉非正整数（整除计算无意义），之后根据keys数值范围选择最优计算方式：

1. 场景A：keys最大值≤1e6：采用筛法计算可整除度
   遍历1到最大值的所有整数，如果该数在keys中存在，则给它所有倍数的可整除度累加该数的出现频率，时间复杂度为O(m log m)，m为keys的最大值
2. 场景B：keys最大值>1e6但不同元素数量少：采用因子枚举法
   对每个不同的元素，枚举它的所有正因子，累加所有因子的出现频率得到该元素的可整除度，时间复杂度为O(k√m)，k为不同元素的数量

优化后代码（适配场景A，最常用场景） #

import java.util.Arrays;
import java.util.List;
import java.util.HashMap;
import java.util.Map;

public static List<Integer> encryptionValidity(int instructionCount, int validityPeriod, List<Integer> keys) {
    // 统计正整数出现频率，同时记录最大值
    Map<Integer, Integer> freqMap = new HashMap<>();
    int maxKey = 0;
    for (int num : keys) {
        if (num <= 0) continue;
        freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
        maxKey = Math.max(maxKey, num);
    }
    if (freqMap.isEmpty()) {
        return Arrays.asList(0, 0);
    }

    // 筛法计算每个数的可整除度
    int[] divDegree = new int[maxKey + 1];
    for (int x = 1; x <= maxKey; x++) {
        Integer count = freqMap.get(x);
        if (count == null) continue;
        for (int multiple = x; multiple <= maxKey; multiple += x) {
            divDegree[multiple] += count;
        }
    }

    // 查找最大可整除度
    int maxDegree = 0;
    for (int num : freqMap.keySet()) {
        maxDegree = Math.max(maxDegree, divDegree[num]);
    }

    // 阈值计算用long避免溢出
    long s = (long) maxDegree * 100000;
    long threshold = (long) instructionCount * validityPeriod;

    return threshold > s ? Arrays.asList(1, (int)s) : Arrays.asList(0, 0);
}

优化效果 #

• 当keys长度为1e4时，原代码需要1亿次运算，优化后仅需要几万次运算，性能提升上千倍
• 修正了原代码的数值计算错误，返回结果符合需求
• 移除了不必要的BigInteger操作，减少了内存开销和运算耗时

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