丑数 - 大师兄

1. 题目描述

把只包含因子 2、3 和 5 的数称作丑数（Ugly Number）。例如 6、8 都是丑数，但 14 不是，因为它包含因子 7。习惯上我们把 1 当做是第一个丑数。求按从小到大的顺序的第 1500 个丑数。

2. 解题思路

2.1 思路一

根据定义，将给定的数不断除 2、3、5，看看能不能除尽即可。然后从 1 遍历到 1500。

2.2 思路二

前面速度慢是因为计算了太多非丑数。根据丑数定义，每一个丑数都是根据前面一个丑数乘以 2、3 或者 5 得到的。

在确保顺序的情况下，逐步计算即可。

3. 代码

3.1 思路一实现

// 判断是否符合丑数定义
function isUgly(number) {
  while (number % 2 === 0) {
    number /= 2;
  }
  while (number % 3 === 0) {
    number /= 3;
  }
  while (number % 5 === 0) {
    number /= 5;
  }
  return number === 1;
}

// 找出 [1, index) 之中的所有丑数
function getUglyNumber(index) {
  if (index <= 0) return 0;

  let number = 0,
    uglyFound = 0;

  while (uglyFound < index) {
    ++number;
    if (isUgly(number)) {
      ++uglyFound;
    }
  }

  return number;
}

3.2 思路二实现

function getUglyNumber(index) {
  if (index <= 0) return 0;

  const uglyNum = [1]; // 存放丑数
  // 2，3，5 三个因子各自的指针
  let pointer2 = 0,
    pointer3 = 0,
    pointer5 = 0;

  for (let i = 1; i < index; ++i) {
    // 找出下一个丑数，确保顺序
    uglyNum[i] = Math.min(
      uglyNum[pointer2] * 2,
      uglyNum[pointer3] * 3,
      uglyNum[pointer5] * 5
    );
    // 如果结果相同，移动指针，防止下次重复计算
    if (uglyNum[i] == uglyNum[pointer2] * 2) ++pointer2;
    if (uglyNum[i] == uglyNum[pointer3] * 3) ++pointer3;
    if (uglyNum[i] == uglyNum[pointer5] * 5) ++pointer5;
  }

  return uglyNum[index - 1];
}

/**
 * 测试代码
 */

console.log(getUglyNumber(1500)); // 859963392