【每日算法Day 81】面试经典题：关于丑数，你真的理解为什么这么算吗？

【每日算法Day 81】面试经典题：关于丑数，你真的理解为什么这么算吗？

题目链接

LeetCode 面试题 17.09. 第 k 个数[1]

题目描述

有些数的素因子只有 3，5，7，请设计一个算法找出第 k 个数。注意，不是必须有这些素因子，而是必须不包含其他的素因子。例如，前几个数按顺序应该是 1，3，5，7，9，15，21。

示例1

输入：k = 5输出：9

题解

这题和主站的LeetCode 264. 丑数 II是一个意思：​​​Solution {public: int getKthMagicNumber(int k) { vector res(k, 1); int idx3 = 0, idx5 = 0, idx7 = 0; for (int i = 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++; } return res[k-1]; }};

python

class Solution: def getKthMagicNumber(self, k: int) -> int: res = [1] * k idx3, idx5, idx7 = 0, 0, 0 for i in range(1, k): res[i] = min(res[idx3]*3, res[idx5]*5, res[idx7]*7) if res[i] == res[idx3]*3: idx3 += 1 if res[i] == res[idx5]*5: idx5 += 1 if res[i] == res[idx7]*7: idx7 += 1 return res[k-1]

参考资料

[1]

LeetCode 面试题 17.09. 第 k 个数: ​​https://leetcode-cn.com/problems/get-kth-magic-number-lcci/​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。