Java 吸血鬼数字（高效版详解）

先来看题

---

吸血鬼数字是指位数为偶数的数字，可以由一堆数字相乘而得到，而这对数字各包含乘积的一半位数的数字，其中从最初的数字中选取的数字可以任意排序。以两个0结尾的数字是不允许的，例如，下列数字都是“吸血鬼”数字：
1260 = 21 * 60
1827 = 21 * 87
2187 = 27 * 81
写出一个程序，找出4位数的所有吸血鬼数字。

再看代码

---

实现方法有很多种，我主要解析一下网上流传的不知是哪位大牛写的高效率版本。
代码如下：

   public class VampireNum {
	   public static void main(String[] args) {
		   String[] ar_str1, ar_str2;
		   int sum = 0;
		   int from;
		   int to;
		   int i_val;
		   int count = 0;
		//双重循环穷举
		   for (int i = 10; i < 100; i++) {
			//j=i+1避免重复
			   from = Math.max(1000 / i, i + 1);
//			   to = Math.min(10000 / i, 100);
			   for (int j = from; j < 100; j++) {
				   i_val = i * j;
				//如果对100取余等于0，则该4位数位数为00，不符合要求
				//或i_val-i-j对9取余不等于0，也不符合要求
				//不符合要求就从新开始循环，继续查找
				   if (i_val % 100 == 0 || (i_val - i - j) % 9 != 0) {
					   continue;
				}
				   count++;
				//将i_val转换成字符串，然后排序，并进行比较，如果比较结果相等，进行sum+1
				   ar_str1 = String.valueOf(i_val).split("");
				   ar_str2 = (String.valueOf(i) + String.valueOf(j)).split("");
				   Arrays.sort(ar_str1);	
				   Arrays.sort(ar_str2);
				   if (Arrays.equals(ar_str1, ar_str2)) {
					   sum++;
					   System.out.println("第" + sum + "组: " + i + " * " + j + " = " + i_val);
				   }
			   }
		   }
		   System.out.println("共找到" + sum + "组吸血鬼数");
		   System.out.println(count);
	   }
   }

运行结果

---

第1组: 15 * 93 = 1395
第2组: 21 * 60 = 1260
第3组: 21 * 87 = 1827
第4组: 27 * 81 = 2187
第5组: 30 * 51 = 1530
第6组: 35 * 41 = 1435
第7组: 80 * 86 = 6880
共找到7组吸血鬼数 232

解析

---

因：

吸血鬼数字是四位数的。

得出取值范围：

10 <= i < 100
10 <= j < 100
1000 <= i * j < 10000
1000 / i <= j < 10000/i

为避免重复，j 的起始值应等于 i + 1:

i + 1 < = j

当 1000 / i < i+1 时:

i +1 <= j

当 1000 / i > i+1 时:

1000/i <= j

所以区间最小值应该在 j + 1 和 1000 / i 中取最大值：

from = Math.max(1000 / i, i + 1);

因 j < 100 且 j < 10000 / i

当 100 < 10000 / i 时：

j < 100

当 100 > 1000 / i 时：

j < 1000 / i

所以区间最大值应在 100 和 10000 / i 中取最小值：

//			to = Math.min(10000 / i, 100);

为什么这句可以注销呢？

因 i < 100，所以100 永远小于 10000 / i。
得出:

j 始终小于 100。

再看看代码的主体算法部分：

i_val % 100 == 0 || (i_val - i - j) % 9 != 0

因:

末尾两位不能为0

所以能整除100的就过滤掉：

i_val % 100 == 0

假设：

i_val = 1000 * a + 100 * b + 10 * c + d
i_val = i * j
i = 10 * a + b
j = 10 * c + d

得出：

i_val - i - j = 990 * a + 99 * b = 9 * (110 * a + 11 * b)

所以 i_val - i - j 一定能被9整除，不能整除的就过滤掉：

(i_val - i - j) % 9 != 0

总结

---

从结果可以看出，该算法循环次数仅为232次，的确是非常高效率的一个精致的小算法，值得品味和学习。
注：以上解析均为个人理解，如有不妥或错误望指正。同时，有不理解的地方请评论或联系我。