首页 > 其他分享 >Leetcode 1492. n 的第 k 个因子

Leetcode 1492. n 的第 k 个因子

时间:2024-09-19 09:48:29浏览次数:10  
标签:heapq 遍历 int 1492 因数 因子 heap Leetcode

1.题目基本信息

1.1.题目描述

给你两个正整数 n 和 k 。

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

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

1.2.题目地址

https://leetcode.cn/problems/the-kth-factor-of-n/description

2.解题方法

2.1.解题思路

优先队列(堆)+求正整数的因数

2.2.解题步骤

第一步,遍历,获取所有的因数并压入heap堆中

第二步,遍历k次,从小到大从heap堆中弹出因数。如果中间出现堆为空,说明因数数量没有k个,返回-1;反之,最后弹出的一个因数就是题解

3.解题代码

Python代码

import heapq

class Solution:
    def kthFactor(self, n: int, k: int) -> int:
        # 第一步,遍历,获取所有的因数并压入heap堆中
        heap=[]
        for i in range(1,int(n**0.5)+1):
            if n%i==0:
                heapq.heappush(heap,i)
                if i!=n//i:
                    heapq.heappush(heap,n//i)
        # print(heap)
        # 第二步,遍历k次,从小到大从heap堆中弹出因数。如果中间出现堆为空,说明因数数量没有k个,返回-1;反之,最后弹出的一个因数就是题解
        res=0
        for i in range(k):
            if len(heap)==0:
                return -1
            else:
                res=heapq.heappop(heap)
        return res

C++代码

class Solution {
public:
    int kthFactor(int n, int k) {
        priority_queue<int> pq;
        for(int i=1;i<int(sqrt(n))+1;++i){
            if(n%i==0){
                pq.push(-i);
                if(i!=n/i){
                    pq.push(-n/i);
                }
            }
        }
        int res=0;
        for(int j=0;j<k;++j){
            if(pq.size()==0){
                return -1;
            }else{
                res=-pq.top();
                pq.pop();
            }
        }
        return res;
    }
};

4.执行结果

在这里插入图片描述

标签:heapq,遍历,int,1492,因数,因子,heap,Leetcode
From: https://www.cnblogs.com/geek0070/p/18419877

相关文章

  • Day 19 回溯法part01| LeetCode 77.组合,216. 组合总和 III,17. 电话号码的字母组合
    理论基础回溯法(回溯搜索法)回溯函数就是递归函数本质是穷举解决的问题组合问题(不强调元素顺序,需去重)切割问题子集问题:一个N个数的集合里有多少符合条件的子集排列问题(强调元素顺序)棋盘问题:N皇后回溯法模板(可抽象为树形结构——N叉树来解决问题)递归返回值以及......
  • LeetCode_0146. LRU缓存
    题目描述请你设计并实现一个满足LRU(最近最少使用)缓存约束的数据结构。实现LRUCache类:LRUCache(intcapacity)以正整数作为容量capacity初始化LRU缓存intget(intkey)如果关键字key存在于缓存中,则返回关键字的值,否则返回-1。voidput(intkey,intval......
  • Day18 二叉树part08| LeetCode 669. 修剪二叉搜索树 , 108.将有序数组转换为二叉搜索树
    669.修剪二叉搜索树669.修剪二叉搜索树classSolution{publicTreeNodetrimBST(TreeNoderoot,intlow,inthigh){if(root==null)returnnull;//处理节点值<low的情况:当前节点及其左子树的所有节点都不在范围内,继续在其右子树上修......
  • 【每日一题】LeetCode 2332.坐上公交的最晚时间(数组、双指针、二分查找、排序)
    【每日一题】LeetCode2332.坐上公交的最晚时间(数组、双指针、二分查找、排序)题目描述给你一个下标从0开始长度为n的整数数组buses,其中buses[i]表示第i辆公交车的出发时间。同时给你一个下标从0开始长度为m的整数数组passengers,其中passengers[j]表示第......
  • 【数据结构和算法实践-树-LeetCode112-路径总和】
    数据结构和算法实践-树-LeetCode112-路径总和题目MyThought代码示例JAVA-8题目给你二叉树的根节点root和一个表示目标和的整数targetSum。判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于目标和targetSum。如果存在,返回true;否则......
  • Leetcode 315. 计算右侧小于当前元素的个数
    1.题目基本信息1.1.题目描述给你一个整数数组nums,按要求返回一个新数组counts。数组counts有该性质:counts[i]的值是nums[i]右侧小于nums[i]的元素的数量。1.2.题目地址https://leetcode.cn/problems/count-of-smaller-numbers-after-self/description2.解题方法......
  • 代码随想录Day3 | LeetCode 203. 移除链表元素、LeetCode 707. 设计链表、LeetCode 20
    LeetCode203.移除链表元素链表基础概念题,也可以用递归做,不过我们把递归的思想放在更能体现它的LeetCode206.反转链表#Definitionforsingly-linkedlist.#classListNode:#def__init__(self,val=0,next=None):#self.val=val#self.next......
  • 代码随想录Day4 | LeetCode 24. 两两交换链表中的节点、LeetCode 19. 删除链表的倒数
    LeetCode24.两两交换链表中的节点递归思想#Definitionforsingly-linkedlist.#classListNode:#def__init__(self,val=0,next=None):#self.val=val#self.next=nextclassSolution:defswapPairs(self,head:Optional[ListNode......
  • LeetCode415周赛T2 +T3
    最高乘法得分动态规划解决从数组b中选择下标的问题题目描述给你一个大小为4的整数数组a和一个大小至少为4的整数数组b。你需要从数组b中选择四个下标i0,i1,i2,和i3,并且要求满足i0<i1<i2<i3。你的得分将是:a[0]*b[i0]+a[1]*b[i1]+a[2]*b......
  • leetcode232. 用栈实现队列
    leetcode232.用栈实现队列请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(push、pop、peek、empty):实现MyQueue类:voidpush(intx)将元素x推到队列的末尾intpop()从队列的开头移除并返回元素intpeek()返回队列开头的元素booleanempt......