力扣 507. 完美数

题目说明

对于一个 正整数，如果它和除了它自身以外的所有 正因子 之和相等，我们称它为 「完美数」。

给定一个 整数 n， 如果是完美数，返回 true，否则返回 false

提示：

  • 1 <= num <= 10^8

示例

示例 1:

1
2
3
4
输入：num = 28
输出：true
解释：28 = 1 + 2 + 4 + 7 + 14
1, 2, 4, 7, 和 14 是 28 的所有正因子。

示例 2:

1
2
输入：num = 6
输出：true

示例 3:

1
2
输入：num = 496
输出：true

示例 4:

1
2
输入：num = 8128
输出：true

示例 5:

1
2
输入：num = 2
输出：false

笔者理解

此题是一道数学算法问题，在力扣题库中被定义为简单题。

解法

当笔者阅读完此题后，发现此题可以直接暴力求解，但是效率比较低，我们可以采用一次消去两个因子的形式，需要注意1不是完美数，让我们来看看具体如何实现的吧。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    /**
     * 模拟
     */
    public boolean checkPerfectNumber(int num) {
        int tick = 0;

        // 求因子时我们可以一次计算两个因子
        for (int i = 2; i < (int) Math.sqrt(num) + 1; i++) {
            if (num % i == 0) {
                tick += i;
                // 排除出现开方因子的可能
                if (i * i != num) {
                    tick += num / i;
                }
            }
        }

        // tick + 1 是因为还存在 1 这个因子，此外还需要排除 num = 1 的情况
        return num == tick + 1 && num != 1;
    }
}

时间效率还行，空间效率一般，可见此解法还比较适合此题。

image-20211231152049174

总结

本题是今天的每日一题，难度是为简单，感兴趣的朋友都可以去尝试一下，此题还有其他更多的解法，朋友们可以自己逐一尝试。