题目链接
LeetCode 面试题 17.09. 第 k 个数[1]
题目描述
有些数的素因子只有 3，5，7，请设计一个算法找出第 k 个数。注意，不是必须有这些素因子，而是必须不包含其他的素因子。例如，前几个数按顺序应该是 1，3，5，7，9，15，21。
示例1
输入：k = 5输出：9
题解
这题和主站的LeetCode 264. 丑数 II是一个意思：
https://leetcode-cn.com/problems/ugly-number-ii/
最直观的想法就是，假设已经生成了 N个丑数，那么我们把每个丑数都乘上 3，5，7，得到的结果中大于已经生成的所有丑数并且最小的那个就是下一个丑数。
但是这样会产生很多重复的丑数，所以也可以用一个优先队列，将已经生成的丑数从小到大保存下来。然后取出队首最小的那个丑数，给它乘上 3，5，7，将新的三个数入队，并且队首的这个数出队，这样就不会再产生重复的数了。
上面这种方法已经可以过这道题了，但是还有更简单的方法。
这么做为什么是对的呢？我们将 数组写成三行相同的形式：
c++
classSolution { public: intgetKthMagicNumber(intk) { vector<int>res(k, 1); intidx3=0, idx5=0, idx7=0; for (inti=1; i<k; ++i) { res[i] =min(res[idx3]*3, min(res[idx5]*5, res[idx7]*7)); if (res[i] ==res[idx3]*3) idx3++; if (res[i] ==res[idx5]*5) idx5++; if (res[i] ==res[idx7]*7) idx7++; } returnres[k-1]; } };
python
classSolution: defgetKthMagicNumber(self, k: int) ->int: res= [1] *kidx3, idx5, idx7=0, 0, 0foriinrange(1, k): res[i] =min(res[idx3]*3, res[idx5]*5, res[idx7]*7) ifres[i] ==res[idx3]*3: idx3+=1ifres[i] ==res[idx5]*5: idx5+=1ifres[i] ==res[idx7]*7: idx7+=1returnres[k-1]
参考资料
[1]
LeetCode 面试题 17.09. 第 k 个数: https://leetcode-cn.com/problems/get-kth-magic-number-lcci/
作者简介：godweiyang，知乎同名，华东师范大学计算机系硕士在读，方向自然语言处理与深度学习。喜欢与人分享技术与知识，期待与你的进一步交流~
