LEETCODE 1390. Four Divisors 解题思路分析

题目大意:

四因数

给你一个整数数组 nums,请你返回该数组中恰有四个因数的这些整数的各因数之和。

如果数组中不存在满足题意的整数,则返回 0 。

示例:

输入:nums = [21,4,7]
输出:32
解释:
21 有 4 个因数:1, 3, 7, 21
4 有 3 个因数:1, 2, 4
7 有 2 个因数:1, 7
答案仅为 21 的所有因数的和。

提示:

  • 1 <= nums.length <= 10^4
  • 1 <= nums[i] <= 10^5

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1390

解题思路分析:

本题没有投机取巧的办法,我们必须求出数组中每一个数字的因数个数,然后再将因数个数为4的所有因数和累加至返回结果。

本题唯一需要强调的一个知识点是如何求一个数字num的质数个数。理论上最笨的方式是从1遍历至num,看num与哪些数字的余数为0即可,但这种做法明显效率不高。其实,当i是num的一个因子时,那么num/i也一定是num的另一个因子,比如3是27的一个因子,那么27/3=9也是27的一个因子,我们实际上同时找到了2个因子。不过唯一的例外是当因子是数字的平方根时,比如3是9的一个因子,这时 9/3 同样还是3,这时我们实际上只找到了一个因子而已。因此循环时,我们只需要从1循环至num的平方根即可,比如数字9,我们只要从1循环至3,就能遍历出9的所有因子。

实现代码:

public int sumFourDivisors(int[] nums) {
    int res=0; // 返回结果
    // 循环每一个数字,将其因子和加入返回结果
    for(int num : nums){
        res+=sumDivisors(num);
    }
    return res;
}
// 计算数字num的因子和
// 如果数字num不是正好包含4个因子,返回0
int sumDivisors(int num){
    // 数字num的平方根
    int sqrt=(int)Math.sqrt(num);
    // 因子个数
    int count=0;
    // 因子和
    int sum=0;
    // 从1循环至num的平方根
    for(int i=1;i<=sqrt;i++){
        // 如果num与i的余数为0。
        if(num%i==0) {
            // 如果num与i的商等于i,说明我们找到了1个因子
            if(num/i==i){
                count+=1;
                sum+=i;
            }else{ 我们找到了2个因子
                count+=2;
                sum+=(i+num/i);
            }
            if(count>4) break;
        }
    }
    // 当因子数为4时,返回因子的和,反之返回0
    return count==4?sum:0;
}

本题解法执行时间为13ms。

Runtime: 13 ms, faster than 92.85% of Java online submissions for Four Divisors.

Memory Usage: 41.5 MB, less than 100.00% of Java online submissions for Four Divisors.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: https://leetcode.jp/leetcode-1390-four-divisors-解题思路分析/
此条目发表在leetcode分类目录,贴了, , , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。