【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(nlogn)$，$n$为传入的参数大小
• 空间复杂度：$O(n)$，$n$为传入的参数大小

十【代码实现】

1. 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;}
}

2. 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

3. 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;}
};

十一【提交结果】

1. Java语言版
   

2. Python语言版
   

3. C++语言版