对上一篇吸血鬼数算法的优化

这是我在博客园的博客中的文章。

下面是原文（未大改，稍作了一些格式上的调整）：

在本人上一篇拙作中，介绍了吸血鬼数的概念并实现了一种算法，但正如末尾所说，在计算从0到 Integer.MAX_VALUE 之间的吸血鬼数时，其计算时间达到了12分钟之长。因此，该算法有待优化。

先说一下该算法的基本思想：比方说要求四位数、即求1000~9999之间的吸血鬼数，那么两个乘数的位数为2，则乘数的范围即可定为[10, 99]，于是，对两个乘数进行从10到99的双层循环，计算其积，在满足相关限制条件的情况下，将积所包含的数字和乘数所包含的数字进行比较，如果数字完全相同，那么该积即为吸血鬼数。对于其它偶数位的整数，可按上述方法类推。

在修改之前的算法基本流程如下：

获得要求的整数区间[m, n]的最小偶数位数a和最大偶数位数b；
因为要分为两个数，所以取a/2位数的最小值min作为初始计数值，取b/2位数的最大值 max作为终止计数值；
从min到max进行双层循环；
判断循环数是否符合要求（末尾不能全为0，etc.）；
将双层循环的数进行相乘；
判断积的大小及位数是否符合要求；
将积的数字和乘数的数字进行比较，如果满足条件则为吸血鬼数。

实际上，由于偶数位之间存在奇数位，上一篇中由于未去除奇数位，从而导致奇数位也加入了循环，故计算时间大大增加。优化后，算法的基本流程如下：

获得要求的整数区间[m, n]的最小数m及最大数n的位数，分别为a、b；
取出[a, b]之间的偶数列表，记为L（在此之前要判断a、b的大小是否合法）；
对L进行循环，每取出其中一个偶数x，就根据x求得对应x位偶数的乘数范围[p, q]；
从p到q进行双层循环；
相关条件判断及积的计算；
积的数字和乘数的数字比较，满足条件则为吸血鬼数。
继续对L的循环。

从上述流程可以看出，虽然循环加了一层，但避开了对奇数位的循环，所以可以猜想整个计算时间应该是第一种的一半左右。经实际测试，计算从0到 Integer.MAX_VALUE 之间的吸血鬼数的时间消耗为380699ms，大约为6分多钟，确实节省了一半时间。

附：整个算法的Java代码实现

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

public class VampireNumber {

    public static void find(int start, int end) {
        System.out.println("start: " + start + ", end: " + end);
        int slen = VampireNumber.getIntegerLength(start);
        int elen = VampireNumber.getIntegerLength(end);

        if(slen >= elen) {
            System.out.println("No suitable number exists in this region.");
            return;
        }

        // 该线性表用作偶数位数存放列表
        List<Integer> lenList = new ArrayList<Integer>((elen - slen + 1) / 2 + 1);
        for(int n = slen; n <= elen; n++) {
            if(n % 2 == 0) {
                lenList.add(n);
            }
        }

        // 开始对列表循环
        for(int len : lenList) {
            int begin = (int)Math.pow(10, len / 2 - 1);　　// 对应len位偶数的、满足位数要求的最小乘数
            int finish = begin * 10;　　　　　　　　　　　// 对应len位偶数的、满足位数要求的最大乘数
            for(int i = begin; i < finish; i++) {
                boolean boundryReached = false;　　　　 // ①（见②和处③的解释）
                for(int j = i; j < finish; j++) {　　　　　　　 //  j从i开始计数，避免出现(i, j)为(17, 27)、(27, 17)这样的重复情况
                    if(i % 10 == 0 && j % 10 == 0) {　　　  // 两个乘数末尾都为0的情况不满足条件，跳过
                        continue;
                    }

                    int value = i * j;
                    if(value < 0 || value > end) {　　　　　　// 如果积已经溢出或者超过最大值
                        if(j == i) {　　　　　　　　　　　　　 // ② 如果j等于i，说明从此之后，无论i的增长或者j的增长都不会再满足条件，所以需要跳出两层循环（见①和③）
                            boundryReached = true;
                        }
                        break;
                    }
                    if(value < start) {　　　　　　　　　　　// 如果积小于最小值，则继续
                        continue;
                    }

                    if(VampireNumber.getIntegerLength(value) != len) {　　// 如果积的位数不是期望位数
                        continue;
                    }

                    int[] numList = new int[10];　　　　　　　　　　　　　　// 十个数字的计数数组，索引0~9分别代表数字0~9出现的次数
                    VampireNumber.getNumberCountList(numList, i, j);　　 // 一个数字出现了几次，就将该计数数组对应索引的值加1

                    while(value != 0) {
                        numList[value % 10]--;　　　　　　   // 将积中出现的数字在数组中对应索引的值减1
                        value /= 10;
                    }
                    boolean isVampireNumber = true;
                    for(int a = 0; a < numList.length / 2 + 1; a++) {　　　　// 循环，用于判断计数数组的每一项是否都为0，如果都为0，说明积是吸血鬼数
                        if(numList[a] != 0 || numList[numList.length - a - 1] != 0) {
                            isVampireNumber = false;
                            break;
                        }
                    }

                    if(isVampireNumber) {　　　　　　　　// 如果是吸血鬼数，则打印出来
                        System.out.println("A vampire number found: " + i * j + ", (" + i + ", " + j + ").");
                    }
                }

                if(boundryReached) {　　　　　　　　　  // ③ 在出现溢出或者超过最大值、并且j等于i的情况下跳出外层循环，因为内层循环的初始条件是j=i，所以此时i再增长的话肯定会溢出或者超过最大值（见①和②）
                    break;
                }
            }
        }
    }

    public static int[] getNumberCountList(int[] list, int... nums) {
        for(int num : nums) {
            do {
                list[num % 10]++;
                num /= 10;
            }while(num != 0);
        }
        return list;
    }

    public static int getIntegerLength(int num) {
        int len = 0;
        do {
            len++;
            num /= 10;
        }while(num != 0);
        return len;
    }

    public static void main(String[] args) {
        System.out.println("-------------- Now start computing... --------------");
        long s = System.currentTimeMillis();
        VampireNumber.find(0, Integer.MAX_VALUE);　　// 调用find()函数来求从0到Integer.MAX_VALUE之间的所有吸血鬼数
        //VampireNumber.find(0, 900000);
        long f = System.currentTimeMillis();
        System.out.println("------- Computing finished, time used: " + (f - s) + " ms. -------");
    }
}