LEETCODE 1492. The kth Factor of n 解题思路分析

题目大意:

n 的第 k 个因子

给你两个正整数 n 和 k 。

如果正整数 i 满足 n % i == 0 ,那么我们就说正整数 i 是整数 n 的因子。

考虑整数 n 的所有因子,将它们 升序排列 。请你返回第 k 个因子。如果 n 的因子数少于 k ,请你返回 -1 。

示例 1:

输入:n = 12, k = 3
输出:3
解释:因子列表包括 [1, 2, 3, 4, 6, 12],第 3 个因子是 3

示例 2:

输入:n = 7, k = 2
输出:7
解释:因子列表包括 [1, 7] ,第 2 个因子是 7 。

示例 3:

输入:n = 4, k = 4
输出:-1
解释:因子列表包括 [1, 2, 4] ,只有 3 个因子,所以我们应该返回 -1 。

示例 4:

输入:n = 1, k = 1
输出:1
解释:因子列表包括 [1] ,第 1 个因子为 1 。

示例 5:

输入:n = 1000, k = 3
输出:4
解释:因子列表包括 [1, 2, 4, 5, 8, 10, 20, 25, 40, 50, 100, 125, 200, 250, 500, 1000] 。

提示:

  • 1 <= k <= n <= 1000

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

解题思路分析:

这道题的数据规模并不大,因此我们可以暴力求解n的第k个因子。我们从1循环至n,如果当前数可以被n整除,那么它即是n的一个因子,并将k减一。当k变为0时,当前数字即是n的第k个因子。如果循环结束后k仍大于0,返回-1。这种解法的时间复杂度为O(n),空间复杂度为O(1)。

引申思考一下,如果本题n的范围是1亿的话,那么我们最坏需要循环1亿次才能得出结果,显然O(n)的时间复杂度难以胜任。此时我们可以以牺牲空间的方式来节约时间。解题时我们只需要循环至sqrt(n)即可,如果当前数字i可以被n整除,那么n/i这个数字同样可以被n整除,换句话说,每当找到n的一个因子时,实际上我们同时找到了它的一对因子,唯一的例外是i等于i/n。我们将所有找到的因子保存至List集合,然后再按照升序排序。如果List的元素个数小于k时,返回-1,反之返回list中第k个元素即可。这样时间复杂度就降至O(sqrt(n)),但空间复杂度会变为O(n),n为所有因子个数。

实现代码1:暴力解法

public int kthFactor(int n, int k) {
    for(int i=1;i<=n;i++){
        if(n%i==0) k--;
        if(k==0) return i;
    }
    return -1;
}

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

Runtime: 0 ms, faster than 100.00% of Java online submissions for The kth Factor of n.

Memory Usage: 36.5 MB, less than 100.00% of Java online submissions for The kth Factor of n.

实现代码2:集合加排序

public int kthFactor(int n, int k) {
    PriorityQueue<Integer> q = new PriorityQueue<>(); // 升序保存每一个因子
    for(int i=1;i*i<=n;i++){ // 从1循环至根号n
        if(n%i ==0){ // 如果当前数字可以被n整除
            q.offer(i); // 当前数字是一个因子,加入到queue
             // n/i也一定是一个因子,
             // 如果 i不等于n/i,将n/i也加入到queue
            if(i*i!=n) q.offer(n/i);
        }
    }
    while(q.size()>0){ // 从queue中取出第k个元素即是返回结果
        int num=q.poll();
        if(--k==0) return num;
    }
    return -1;     
}

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

Runtime: 1 ms, faster than 80.18% of Java online submissions for The kth Factor of n.

Memory Usage: 36.2 MB, less than 100.00% of Java online submissions for The kth Factor of n.

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

发表评论

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