这是悦乐书的第249次更新，第262篇原创
01 看题和准备
今天介绍的是LeetCode算法题中Easy级别的第116题（顺位题号是507）。我们定义Perfect Number是一个正整数，它等于除了它自己之外的所有正除数之和。现在，给定一个整数n，编写一个函数，当它是一个完美数字时返回true，否则返回false。例如：
输入：28
输出：true
说明：28 = 1 + 2 + 4 + 7 + 14
注意：输入数字n不会超过100,000,000。（1E8）
本次解题使用的开发工具是eclipse，jdk使用的版本是1.8，环境是win7 64位系统，使用Java语言编写和测试。
02 第一种解法
特殊情况：最小Perfect Number为6，奇数不可能是Perfect Number
正常情况：num对从2开始的正整数做取余操作，等于0，就表示能够被整除，将能够被整除的数累加起来，最后判断与num是否相等。在循环中，我们可以将num除以2再判断，而不必一直遍历到num，因为超过num/2的数再乘以另外一个数（1除外）肯定会大于num。
此解法的时间复杂度是O(n)，其中n只用判断n/2次，空间复杂度是O(1)。
public boolean checkPerfectNumber(int num) {
if (num < 6 || num%2 != 0) {
return false;
}
int sum = 1;
for (int i=2; i<=num/2; i++) {
if (num%i == 0) {
sum += i;
}
}
return sum == num;
}
03 第二种解法
我们是不是可以将for循环中的循环次数再缩小一点？第一种解法是num/2次，而一个正整数它所包含的因子，两两相乘，当两因子无限逼近的时候，就是正整数的平方根，但是使用平方根作为循环次数的上限，会把右边的因子排除掉，所以我们需要提前就加进去，当num能被当前因子整除时，它的商就是右边的一个因子，所以需要将两个因子都加上。最后还是判断因子之和是否与num相等。
此解法的时间复杂度是O(n)，其中n只用判断根号n次，空间复杂度是O(1)。
public boolean checkPerfectNumber2(int num) {
if (num < 6 || num%2 != 0) {
return false;
}
int sum = 1;
for (int i=2; i<=Math.sqrt(num); i++) {
if (num%i == 0) {
sum += i + num/i;
}
}
return sum == num;
}
04 第三种解法
最小的Perfect Number是6，接着是28，然后是496
6: 2x3 true
28: 4x7 true
120: 8x15 false
496: 16x31 true
2016: 32x63 false
8128: 64x127 true
上面这些数，可以看做2的(n-1)次方与2的n次方再减1的乘积，其中n从2开始，但是并非所有的n都符合，在上面几个数中，当n等于4和6时是不符合Perfect Number的，这里直接给出符合的数吧，2,3,5,7,13,17,19,31，至于17,19,31这几个次方数，做乘法会溢出，可以直接不考虑，至于为什么是这几个数，可以一个一个往下推，不难。当然，你要是把int范围内的5个Perfect Number(第5个是33550336)都找出来了，直接做判断也行。
public boolean checkPerfectNumber3(int num) {
int[] primes = {2,3,5,7,13};
for (int p: primes) {
if ((1 << (p - 1)) * ((1 << p) - 1) == num) {
return true;
}
}
return false;
}
05 小结
算法专题目前已日更超过三个月，算法题文章116+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。
以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！
网友评论