【LeetCode每日一题】—

【LeetCode每日一题】——LCR 168.丑数

文章目录

一【题目类别】
二【题目难度】
三【题目编号】
四【题目描述】
五【题目注意】
六【题目示例】
七【题目提示】
八【解题思路】
九【时间频度】
十【代码实现】
十一【提交结果】

一【题目类别】

优先队列

二【题目难度】

中等

三【题目编号】

LCR 168.丑数

四【题目描述】

给你一个整数 n ，请你找出并返回第 n 个丑数。
说明：丑数是只包含质因数 2、3 和/或 5 的正整数；1 是丑数。

五【题目注意】

本题与主站 264 题相同：https://leetcode-cn.com/problems/ugly-number-ii/

六【题目示例】

示例 1：
- 输入: n = 10
- 输出: 12
- 解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。

七【题目提示】

1 <= n <= 1690

八【解题思路】

其实这道题目很经典，一般我们使用动态规划解决
不过我们本周的Topic为优先队列，所以使用小顶堆解决该问题
思路其实都一样，首先将第一个丑数加入到小顶堆中，然后依次计算后面的丑数（丑数 * 2/3/5 = 丑数）并将其加入到小顶堆（还要注意不要加入重复的计算值，所以需要用到哈希表）
每次加入新的值之前都要以上一次计算的结果为基础（即弹出的堆顶元素）
使用计数器判断是否得到目标数量的丑数
最后返回结果即可

九【时间频度】

时间复杂度： $O (n l o g n)$ ， $n$ 为传入的参数大小
空间复杂度： $O (n)$ ， $n$ 为传入的参数大小

十【代码实现】

Java语言版

class Solution {public int nthUglyNumber(int n) {// 初始化小顶堆和哈希表PriorityQueue<Long> heap = new PriorityQueue<Long>();Set<Long> hashMap = new HashSet<Long>();// 将第一个丑数加入到小顶堆和哈希表中heap.offer(1L);hashMap.add(1L);// 计算第n个丑数long res = 1;while (n > 0) {res = heap.poll();// 丑数 * 2 = 丑数if (!hashMap.contains(res * 2)) {heap.offer(res * 2);hashMap.add(res * 2);}// 丑数 * 3 = 丑数if (!hashMap.contains(res * 3)) {heap.offer(res * 3);hashMap.add(res * 3);}// 丑数 * 5 = 丑数if (!hashMap.contains(res * 5)) {heap.offer(res * 5);hashMap.add(res * 5);}// 计数用n--;}// 返回结果return (int)res;}
}

Python语言版

class Solution:def nthUglyNumber(self, n: int) -> int:# 初始化小顶堆和哈希表res = 0hashMap = set()heap = []# 将第一个丑数加入到小顶堆和哈希表中heapq.heappush(heap, 1)hashMap.add(1)# 计算第n个丑数while n > 0:res = heapq.heappop(heap)# 丑数 * 2 = 丑数if res * 2 not in hashMap:heapq.heappush(heap, res * 2)hashMap.add(res * 2)# 丑数 * 3 = 丑数if res * 3 not in hashMap:heapq.heappush(heap, res * 3)hashMap.add(res * 3)# 丑数 * 5 = 丑数if res * 5 not in hashMap:heapq.heappush(heap, res * 5)hashMap.add(res * 5)# 计数用n -= 1# 返回结果return res

C++语言版

class Solution {
public:int nthUglyNumber(int n) {// 初始化小顶堆和哈希表priority_queue<long, vector<long>, greater<long>> heap;unordered_set<long> hashMap;long res = 0;// 将第一个丑数加入到小顶堆和哈希表中heap.push(1);hashMap.insert(1);// 计算第n个丑数while (n > 0) {res = heap.top();heap.pop();// 丑数 * 2 = 丑数if (hashMap.find(res * 2) == hashMap.end()) {heap.push(res * 2);hashMap.insert(res * 2);}// 丑数 * 3 = 丑数if (hashMap.find(res * 3) == hashMap.end()) {heap.push(res * 3);hashMap.insert(res * 3);}// 丑数 * 5 = 丑数if (hashMap.find(res * 5) == hashMap.end()) {heap.push(res * 5);hashMap.insert(res * 5);}// 计数用n--;}// 返回结果return (int)res;}
};