请求出第20个丑数。(最小因子只有2、3、5的数,称作丑数(Ugly Number)。例如6、8都是丑数,但14不是,因为它包含因子7,习惯上我们把1当做是第一个丑数);
输入:getUglyNumber(20)
输出:36
/* 思路: 1.按顺序将丑数保存在数组中,然后求下一个丑数; 2.下一个丑数是由数组中某个丑数A * 2,B * 3,C * 5中的最小值得来的。 3.按照题目规定,第一个丑数是1,存入数组中; 4.第二个丑数为1*2,1*3,1*5三个中的最小值; 5.第三个丑数为2*2,1*3,1*5三个中的最小值,依次类推,求出第N个数组。 */ function getUglyNumber(index){ if(index === 0) return 0; var uglyArr = [1]; // var index = prompt('请输入一个整数'); // var index = 20; var factor2=0,//定义三个因数 factor3=0, factor5=0; for(var i=1;i<index;i++){ uglyArr[i] = Math.min(uglyArr[factor2]*2,uglyArr[factor3]*3,uglyArr[factor5]*5); if(uglyArr[i] === uglyArr[factor2]*2) factor2++; if(uglyArr[i] === uglyArr[factor3]*3) factor3++; if(uglyArr[i] === uglyArr[factor5]*5) factor5++; } return uglyArr[index-1]; } console.log(getUglyNumber(20)); console.log(getUglyNumber(0)); console.log(getUglyNumber(1));
function getUglyNumber(n) { const memo = [1, 2, 3, 4, 5]; let i = 6; while (memo.length < n) { let result = Math.min( ...[i / 2, i / 3, i / 5].filter((x) => Number.isInteger(x)) ); if (memo.includes(result)) { memo.push(i); } i++; } return memo[n - 1]; }