1. 题目描述
2. 思路
很明显,丑数就是 \(2,3,5\) 的乘积组合。
最一开始,我竟然傻傻的 \(dfs\) + \(set\) 来求解,其实仔细想想,\(dfs\) 肯定是不行的,因为 \(dfs\) 会一条路走到黑。
理想情况下,我们希望每个丑数都按位置放置,而不是跳着来的,例如,\(6\) 之后的丑数应该是 \(8\),而不是 \(9\)。
对于下一个丑数来说,他只有三种可能:
pre1 * 2;
pre2 * 3;
pre3 * 5;
pre1, pre2, pre3
可能是不同的数。我们希望每次都选取这个组合的最小值,并且刚好是下一个丑数。
那么我们就需要保证,pre1,pre2,pre3
不能大了,也不能小,并且它们都是一个个整数。
好吧,我承认我的论述有点乱,从实际的例子出发好了。
最开始,有一个特殊的丑数 \(1\),从 \(1\) 出发,有:
1 * 2 = 2;
1 * 3 = 3;
1 * 5 = 5;
我们应该选择 \(2\),那么,此时 \(pre1\) 也就是 \(1*2\) 中的 \(1\) 就要编程 \(2\) 了,\(2\) 就是 \(1\) 之后的最近的丑数。即:
2 * 2 = 4;
1 * 3 = 3;
1 * 5 = 5;
此时我们应该选择 \(3\),那么,又变成:
2 * 2 = 4;
2 * 3 = 6;
1 * 5 = 5;
选择 \(4\),变成;
3 * 2 = 6;
2 * 3 = 6;
1 * 5 = 5;
选择 \(5\),变成:
3 * 2 = 6;
2 * 3 = 6;
2 * 5 = 10;
选择 \(6\),但是此时有两个 \(6\) 同时出现,我们同时修改 \(pre2\) 和 \(pre3\),因为不可以重复:
4 * 2 = 8;
3 * 3 = 9;
2 * 5 = 10;
那么,自然而然的,我们可以通过一种类似三指针的方式,求解。
3. 代码
class Solution {
public:
int nthUglyNumber(int n) {
int f[n + 10];
f[0] = 1;
int pre1 = 0, pre2 = 0, pre3 = 0;
for(int i = 1; i <= n; i ++ ) {
int a = f[pre1] * 2, b = f[pre2] * 3, c = f[pre3] * 5;
int minx = min({a, b, c});
f[i] = minx;
// 注意下面不能都用if-else
// 因为丑数不可以重复出现
if(a == minx) pre1 ++ ;
if(b == minx) pre2 ++ ;
if(c == minx) pre3 ++ ;
}
return f[n - 1];
}
};
4. 思路2,贪心 + 优先队列 + set
思路就是,每次选取一个最小值 \(x\) ,将它发展出来的三个丑数 \(x*2\), \(x*3\), \(x*5\) 放到优先队列当中。
然后,将每次从优先队列取出来的数放到哈希表中,当放入哈希表中的数的个数为 \(n\) 时,就表示我们取出来最小的 \(n\) 个丑数。
然后,就是注意去重就行了。
5. 代码
class Solution {
public:
int nthUglyNumber(int n) {
priority_queue<long long, vector<long long>, greater<long long>> q;
unordered_set<int> s;
int start = 1;
q.push(start);
while(q.size()) {
auto t = q.top(); q.pop();
if(s.count(t)) continue; // 去重
s.insert(t);
if(s.size() == n) return t;
q.push(t * 2);
q.push(t * 3);
q.push(t * 5);
}
return -1;
}
};
6. 总结
其实呢,这题,想到是不太好想,看别人的分析也不太容易看懂,但是看代码就一看就懂了。
其实这题,就像贪心,因为丑数只能从另一个丑数通过 pre1*2,pre2*3,pre3*5
(pre都是丑数),的方式得到,因此,找出 \(n\) 个丑数时很容易的。
难点在于,如何保证这 \(n\) 个丑数恰好是最小的 \(n\) 个呢?贪心呗!
如果,我们希望通过 pre1*2,pre2*3,pre3*5
得到的丑数尽可能的小,那么,pre1, pre2, pre3
当然也要尽可能的小,那么,我们就每次枚举最小的 pre
。
如果使用过了,就要增大 pre
,并且我们希望增大的幅度近可能的小,那么与 \(pre\) 相邻的那个丑数就是最好的选择了!
另外,当我们需要增加 \(pre\) 时,与 \(pre\) 相邻的丑数一定存在,因为只要增大,就意味着我们找到了一个新的丑数。