Appearance
1201. 丑数 III
题目描述
丑数是可以被 a 或 b 或 c 整除的 正整数 。
给你四个整数：n 、a 、b 、c ，请你设计一个算法来找出第 n 个丑数。
示例 1：
- 输入： n = 3, a = 2, b = 3, c = 5
- 输出： 4
- 解释： 丑数序列为 2, 3, 4, 5, 6, 8, 9, 10... 其中第 3 个是 4。
示例 2：
- 输入： n = 4, a = 2, b = 3, c = 4
- 输出： 6
- 解释： 丑数序列为 2, 3, 4, 6, 8, 9, 10, 12... 其中第 4 个是 6。
示例 3：
- 输入： n = 5, a = 2, b = 11, c = 13
- 输出： 10
- 解释： 丑数序列为 2, 4, 6, 8, 10, 11, 12, 13... 其中第 5 个是 10。
提示：
- 1 <= n, a, b, c <= 109
- 1 <= a * b * c <= 1018
- 本题结果在
[1, 2 * 109]的范围内
难度： Medium
题解代码
javascript
/**
* @param {number} n
* @param {number} a
* @param {number} b
* @param {number} c
* @return {number}
*/
// var nthUglyNumber = function(n, a, b, c) {
// return nthSuperUglyNumber(n, [a, b, c])
// };
// var nthSuperUglyNumber = function(n, primes) {
// const dp = [0, 1]
// const p = new Array(primes.length).fill(1)
// for (i = 2; i <= n + 2; i++) {
// const min = Math.min(...[].slice.call(p).map((item, idx) => dp[item] * primes[idx]))
// console.log(min)
// for (let i = 0, l = p.length; i < l; i++) {
// if (dp[p[i]] * primes[i] === min) p[i]++
// }
// dp[i] = min
// }
// console.log(dp)
// return dp[n + 1]
// };
var nthUglyNumber = function(n, a, b, c) {
const isUgly = num => {
return num / a === Math.floor(num / a) || num / b === Math.floor(num / b) || num / c === Math.floor(num / c)
}
let count = 1
let idx = 1
// let arr = []
while(count <= n) {
idx++
if (isUgly(idx)) {
count++
// arr.push(idx)
}
}
// console.log(arr, count)
return idx
};