丑数

function GetUglyNumber_Solution(index)
{
    // write code here
    if(index < 7) return index
    let p2 = 0, p3 = 0, p5 = 0  //计算下一个丑数的位置
    let res = []  //存放排好序的丑数
    res[0] = 1
    for(let i =1; i < index; i++){
        res[i] = Math.min(res[p2]*2, Math.min(res[p3]*3,res[p5]*5)) //取最小值
        //移动相应的位置
        if(res[i] === res[p2]*2) p2++;
        if(res[i] === res[p3]*3) p3++;
        if(res[i] === res[p5]*5) p5++;
    }
    //返回最后一个
    return res[index-1];
}

function GetUglyNumber_Solution(index)
{
    // write code here
    if(index == 0){
        return 0;
    }
    var dp = [];
    var i2 = 0, i3 = 0, i5 = 0;
    dp[0] = 1;
    for(var i = 1;i < index;i++){
        dp[i] = Math.min(dp[i2] * 2, dp[i3] * 3, dp[i5] * 5);
        if(dp[i] == dp[i2] * 2){
            i2++;
        }
        if(dp[i] == dp[i3] * 3){
            i3++;
        }
        if(dp[i] == dp[i5] * 5){
            i5++;
        }
    }
    return dp[index - 1];
}

var isUgly = function(num) {
if(num <= 0) {
    return false
}
while(true){
    if(num == 1 || num == 2 || num == 3 || num ==5){
        return true
    }
    if(num % 2 == 0){
        num /= 2
    }else if(num % 3 == 0){
        num/=3
    }else if(num % 5 == 0){
        num /= 5 
    }else{
        return false
    }
}
};

function GetUglyNumber_Solution(index)
{
    // write code here
    let p2 = 1, p3 = 1, p5 = 1
    const dp = new Array(index+1)
    dp[0] = 0
    dp[1] = 1
    for(let i = 2;i<=index;i++){
        dp[i] = Math.min(dp[p2]*2, dp[p3]*3, dp[p5]*5)
        if(dp[i] == dp[p2]*2) p2++
        if(dp[i] == dp[p3]*3) p3++
        if(dp[i] == dp[p5]*5) p5++
    }
    return dp[index]
}
module.exports = {
    GetUglyNumber_Solution : GetUglyNumber_Solution
};

function GetUglyNumber_Solution(index)
{
    if(index<7){
        return index
    }
    var res=[];
    res[0]=1;
    var t2=0,t3=0,t5=0;
    for(var i=1;i<index;i++){
        res[i]=Math.min(res[t2]*2,Math.min(res[t3]*3,res[t5]*5));
        if(res[i]===res[t2]*2)
            t2++;
        if(res[i]===res[t3]*3)
            t3++;
        if(res[i]===res[t5]*5)
            t5++;
    }
    return res[index-1]// write code here
}

/**
 * 我的解题思路：
 * 1.既然每个丑数都能被2、3、5整除，那么就分别用这三个数去整除每一个数
 * 2.如果整除到最后的结果为1，那么说明这个数就是丑数，否则就继续找下一个数
 * 3.为了保证每次整除的结果不影响初始值，这里在整除前使用新的变量去操作
 * 4.这个方法很好理解，但是遗憾的是超时了
 * 
 * @param {*} index 
 */
function GetUglyNumber_Solution(index)
{
    // write code here
    let num = 1;
    let n = 1;
    const result = [];
    while (num !== index + 1) {
        let cur = n;
        while (cur % 2 === 0) {
            cur = cur / 2;
        }
        while (cur % 3 === 0) {
            cur = cur / 3;
        }
        while (cur % 5 === 0) {
            cur = cur / 5;
        }
        if (cur === 1) {
            num ++;
            result.push(n);
        }
        n ++;
    }
    return result[index - 1];
}

/**
 * 评论区TOP的解题思路：
 * 1.这个想法挺***的，前7个数就不用看了，直接看后面的思路
 * 2.第一个丑数是1，也就是当前index对应的最小丑数，那么我们用这个最小的丑数分别乘以2、3、5，就可以得到3个新的丑数
 * 3.在这三个新的丑数中，我们可以找到最小的，那么它就是下一个最小丑数，它对应的因子为当前最小因子
 * 4.我们用下一个最小丑数乘以当前最小因子之后与其他的两个丑数比较，再次获得一个最小丑数
 * 5.重复3、4步骤，我们就可以得到一个index长度的丑数序列，且按照从小到大排序
 * 6.最后返回数组中第index个丑数即可
 * 
 * @param {*} index 
 */
function topGetUglyNumber_Solution(index)
{
    // write code here
    if (index < 7) return index;
    const res = [1];
    let t2 = 0;
    let t3 = 0;
    let t5 = 0;
    for (let i = 1; i < index; i ++) {
        res[i] = Math.min(res[t2] * 2, Math.min(res[t3] * 3, res[t5] * 5));
        if (res[i] === res[t2] * 2) {
            t2 ++;
        }
        if (res[i] === res[t3] * 3) {
            t3 ++;
        }
        if (res[i] === res[t5] * 5) {
            t5 ++;
        }
    }
    return res[index - 1];
}

解法同第一页高票回答

• 维护三个指针，指向三个对应数组当前值
• 质因子并非因数，比如8=2^3，不是8=2*4这样考虑的

function GetUglyNumber_Solution(index)
{
  // write code here
  // 小于7全是丑数
  if (index < 7) {
    return index;
  }

  let arr = [];
  // 维护三个指针，指向当前队列最小的数
  let p1 = 0, p2 = 0, p3 = 0;
  let newNum = 1;
  arr.push(newNum);

  while (arr.length < index) {
    newNum = Math.min(arr[p1] * 2, arr[p2] * 3, arr[p3] * 5);
    if (newNum === arr[p1] * 2) p1++;
    if (newNum === arr[p2] * 3) p2++;
    if (newNum === arr[p3] * 5) p3++;
    arr.push(newNum);
  }

  // console.log(arr);
  return arr[index - 1];
}

GetUglyNumber_Solution(16);

    function GetUglyNumber_Solution(index) {
      if (index <= 0) {
        return 0;
      }
      let arr = [1];
      let i2 = i3 = i5 = 0;
      let cur = 0;
      while (arr.length < index) {
        arr.push(Math.min(arr[i2] * 2, arr[i3] * 3, arr[i5] * 5));
        const current = arr[arr.length - 1];
        while (arr[i2] * 2 <= current) {
          i2++;
        }
        while (arr[i3] * 3 <= current) {
          i3++;
        }
        while (arr[i5] * 5 <= current) {
          i5++;
        }
      }
      return arr[index - 1];
    }

function GetUglyNumber_Solution(index)
{
    //index小于1，则返回0
    if(index<1){
        return 0;
    }
    //index等于1，选择第1个丑数，返回”1“
    if(index==1){
        return 1;
    }
    
    var chou = [1];  //保存从小到大的丑数，第一个为1.
    var count=1;     //count用于计算当前已获得的丑数数量
    var two=0,three=0,five=0;  //用于作为计算丑数的因子，第一个丑数1不与2、3、5相乘，所以2、3、5初始化为0
    var i=1;
    //while循环，直到计算到第index个丑数时结束
    while(count < index){
        //在第一个丑数的基础上，分别乘以因子2、3、5，然后选出其中最小的一个数存入number。
        var number = Math.min(chou[two]*2,chou[three]*3,chou[five]*5);
        //number为丑数乘以2得到的
        if(number == chou[two]*2){
            two++;
        }
        //number为丑数乘以3得到的
        if(number == chou[three]*3){
            three++;
        }
        //number为丑数乘以5得到的
        if(number == chou[five]*5){
            five++;
        }
        //将丑数写入数组，count加1
        chou[i++] = number;
        count++;
    }
    return chou[i-1];
}

function GetUglyNumber_Solution(index)
{
    if(index <=0) return 0;
    let uglyArr = [1], idx2 = idx3 = idx5 = 0, i;
    for(i = 1; i < index; ++i){
        uglyArr[i] = Math.min(uglyArr[idx2]*2, uglyArr[idx3]*3, uglyArr[idx5]*5);
        if(uglyArr[i] === uglyArr[idx2]*2) ++idx2;
        if(uglyArr[i] === uglyArr[idx3]*3) ++idx3;
        if(uglyArr[i] === uglyArr[idx5]*5) ++idx5;
    }
    return uglyArr[index-1];
}

function GetUglyNumber_Solution(index)
{
    if(index == 0){
        return 0;
    }
    var arr = new Array(index);
    arr[0] = 1;
    var fac2 = 0,
        fac3 = 0,
        fac5 = 0;
    for(var i=1; i<arr.length; i++){
        var min = Math.min(arr[fac2]*2, arr[fac3]*3, arr[fac5]*5);
        arr[i] = min;
        while(arr[fac2]*2 <= min){
            fac2++;
        }
        while(arr[fac3]*3 <= min){
            fac3++;
        }
        while(arr[fac5]*5 <= min){
            fac5++;
        }
    }
    return arr[arr.length-1];
}