题目 ugly-number-ii
编写一个程序，找出第 n 个丑数。
丑数就是只包含质因数 2, 3, 5 的正整数。
Write a program to find the n-th ugly number.
Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.
Example:
Input: n = 10
Output: 12
Explanation: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.
Note:
1 is typically treated as an ugly number.
n does not exceed 1690.
理解
方法1
时间复杂度：o（n3）
全部丑数都找出来
MAX最大的整数
i [1--MAX] i2
j[ i--MAX] j3
k[j--MAX] k*5
方法2 bfs 树的层次遍历
输出结果：
[1 ,2 ,3 ,5, 4,6,10,6,9,15,10,15, 25,8,12,20]
期望结果：
【 1, 2, 3, 4, 5, 6, 8, 9, 10, 12】
- 问题1：顺序不对
10=2*5
9=3×3
但是按照顺序 9，10
【 1, 2, 3, 4, 5, 6, 8, 9, 10, 12】
- 问题2 重复数据
6=2×3
6=3*2
解决办法：
需要2个结构队列完成遍历，
- 保证完成层次遍历
- priority_queue
- 判断是否重复元素：（）
std::map :时间复杂度 log(n)
std::set ： 时间复杂度 log(n),不能通过下标访问
unordered_map：时间复杂度理想情况下 o(1)
性能测试
long 2147483648～2147483647
long long的最大值：9223372036854775807
long long的最小值：-9223372036854775808
实现
我的实现c++
class Solution {
public:
int nthUglyNumber(int n)
{
priority_queue<long long,vector<long long>,greater<long long> > queue;
unordered_map<long long,bool> repeat;
queue.push(1);
repeat[1]=true;
int array[3]={2,3,5};
long long number=1;
int i=0;
while(!queue.empty()&&i++<n)
{
number=queue.top();
queue.pop();//按照从小到大顺序 greater
for(int i=0;i<3;i++)
{
long long temp=array[i]*number;
if(repeat[temp] ==false)
{
repeat[temp]=true;
queue.push(temp);
}
}
}
return number;
}
};
别人的实现 golang
func nthUglyNumber(n int) int {
var ugly []int
ugly = append(ugly, 1)
t2, t3, t5 := 0, 0, 0
for n > len(ugly) {
for ugly[t2]*2 <= ugly[len(ugly)-1] {
t2 += 1
}
for ugly[t3]*3 <= ugly[len(ugly)-1] {
t3 += 1
}
for ugly[t5]*5 <= ugly[len(ugly)-1] {
t5 += 1
}
ugly = append(ugly, min(ugly[t2]*2, ugly[t3]*3, ugly[t5]*5))
}
return ugly[n-1]
}
func min(a, b, c int) int{
if a <= b {
b = a
}
if b <= c {
return b
}
return c
}
4 类似题目
4.1 322. Coin Change
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
4.2 测试
输入: coins = [1, 2, 5], amount = 11
输出: 3
解释: 11 = 5 + 5 + 1
4.2 分析