求1到Long.MAX_VALUE范围内Armstrong数的高效算法优化方案

我正在处理一项任务：编写一个方法找出1到N范围内的所有Armstrong数。

在数论中，给定基数b的Armstrong数（也称为自恋数、完全数字不变数（PPDI）或完美数）是指一个数等于其各位数字的位数次幂之和。

现有代码在N < 1000000000时可正常运行，但处理Long.MAX_VALUE时程序始终无法完成，核心问题是遍历所有数字的效率过低。我已预存数字幂次矩阵以避免重复计算，还尝试跳过已找到数字的排列数，但仍效率低下，恳请提供优化思路。

附现有代码：

public class Solution {
    static List<Long> list = new ArrayList<>();
    static int[][] powers;

    public static long[] getNumbers(long N) {
        fillPowers();
        if(N <= 0) {
            return new long[0];
        }
        list.clear();
        long res = 0L;
        for (long i = 1L; i < N; i++) {
            int t = getDigitFromLong(i);
            long temp = i;
            while (temp >= 1) {
                long devidedIntoTen = temp % 10;
                res += powers[t] [(int) devidedIntoTen];
                temp/=10;
            }
            if(res == i) {
                list.add(res);
                res = 0;
            } else {
                res = 0;
            }
        }

        Collections.sort(list);
        long[] l = new long[list.size()];
        for (int i = 0; i < list.size(); i++) {
            l[i] = list.get(i);
        }
        return l;
    }

    public static void fillPowers() {
        int numDigits = getDigitFromLong(Long.MAX_VALUE);
        powers = new int[numDigits][10];

        for (int i = 0; i < numDigits; i++) {
            for (int j = 0; j < 10; j++) {
                powers[i][j] = (int) Math.pow(j, i);
            }
        }
    }

    public static int getDigitFromLong (long number) {
        int numDigits = 0;
        while (number > 0) {
            number /= 10;
            numDigits++;
        }
        return numDigits;
    }

}

优化思路 #

1. 直接预存已知Armstrong数（最优方案） #

十进制中，long范围内的Armstrong数是固定且有限的（共27个），最大的为88593477，远小于Long.MAX_VALUE（9223372036854775807）。直接预存这些数，筛选出小于N的结果即可，完全避免遍历计算，性能拉满。

2. 反向构造+剪枝（若需动态计算而非预存） #

放弃从1到N逐个检查的思路，改为按数字位数分组，生成非递减数字组合（避免重复排列），计算幂次和后验证是否符合Armstrong数条件：

• 按位数d从1到18（long最大位数）分组
• 生成非递减的d位数字组合（如1,1,2而非1,2,1），计算各位d次幂之和sum
• 检查sum的位数是否为d，且sum < N，符合则加入结果集
• 生成过程中提前剪枝：若当前已选数字的幂次和 + 剩余位全取9的幂次和 < 10^(d-1)（d位数最小值），或当前和已超过N，直接终止该分支

3. 修复幂次存储溢出问题 #

原代码用int存储幂次，当d≥10时，9^10=3486784401超过int最大值（2147483647），会导致计算错误。需将powers数组改为long类型。

4. 优化位数计算 #

原getDigitFromLong方法用循环计算位数，可替换为数学公式：(int) Math.log10(number) + 1（仅适用于正整数），减少循环开销。

优化后代码（预存方案） #

import java.util.ArrayList;
import java.util.List;

public class Solution {
    // 预存long范围内的所有Armstrong数
    private static final long[] ALL_ARMSTRONG_NUMBERS = {
        1, 2, 3, 4, 5, 6, 7, 8, 9, 153, 370, 371, 407,
        1634, 8208, 9474, 54748, 92727, 93084, 548834,
        1741725, 4210818, 9800817, 9926315, 24678050,
        24678051, 88593477
    };

    public static long[] getNumbers(long N) {
        if (N <= 0) {
            return new long[0];
        }
        List<Long> result = new ArrayList<>();
        for (long num : ALL_ARMSTRONG_NUMBERS) {
            if (num < N) {
                result.add(num);
            }
        }
        long[] resArray = new long[result.size()];
        for (int i = 0; i < result.size(); i++) {
            resArray[i] = result.get(i);
        }
        return resArray;
    }
}

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