java - 在 Java 上更快地找到所有自恋(阿姆斯特朗)数字

Question

有更有效的方法吗？给定数字 N - 找到所有 < N 的自恋(阿姆斯特朗)数字。这是我的代码，但我想还有更有效的解决方案。另外，也许我们可以通过位运算来解决它？

public static void main(String args[]) throws  Exception
 {
    long a = System.nanoTime();
    int t [] = getNumbers(4_483_647L);
    long b = System.nanoTime();
    System.out.println("Time totally "+(b-a));
    for(int k: t)
        System.out.print(k+" ");
}
public static int[] getNumbers(long N)
{

    int length=1;
    int porog=10, r=1, s=1;
    double k;
    LinkedList<Integer> list = new LinkedList<>();

    for(int i=1; i<N; i++)
    {
        if(i==porog)
        {
            length++;
            porog*=10;
        }
        s = i;
        k=0;
        while(s>0)
        {
            r = s%10;
            k+=Math.pow(r, length);
            if(k>i)break;
            s=s/10;
        }
        if((int)k==i)
            list.add(i);
    }
   int[] result  = new int[list.size()];
    int i=0;
    for(int n: list)
    {
        result[i] = n;
        i++;
    }

    return result;  }  }

Answer 1

一些观察:

• 如果您的初始最大值是 long ，你的结果应该是 long类型也一样，以防万一( int 适合你，因为自恋数字相距很远)
• 如果将返回类型更改为“big”Long ，您可以使用Collections.toArray()将结果重新打包到数组中...
• ...虽然实际上，您应该只返回链接列表...
• 您无需不断重新计算权力。对于外循环中的每个十年，您只需要 i^j，其中 i=0..9，j 是当前十年的位数
• 事实上，您不需要 Math.pow()根本没有，因为你可以在每十年使用乘法

应用上面评论中的想法并更改方法签名，您会得到运行速度大约 30 倍的东西:

public static Long[] getNumbers(long N) {
    int porog = 10;
    LinkedList<Long> list = new LinkedList<>();
    // initial powers for the number 0-9
    long[] powers = { 0l, 1l, 2l, 3l, 4l, 5l, 6l, 7l, 8l, 9l };

    for (long i = 1; i < N; i++) {
        if (i == porog) {
            porog *= 10;
            // calculate i^length
            for (int pi = 1; pi < 10; pi++) {
                powers[pi] *= pi;
            }
        }
        long s = i;
        long k = 0;
        while (s > 0) {
            int r = (int)(s % 10);
            k += powers[r];
            if (k > i)
                break;
            s /= 10;
        }

        if (k == i)
            list.add(i);
    }

    return list.toArray(new Long[]{});
}