丑数

难度:中等

描述:

设计一个算法,找出只含素因子 2,3,5 的第 n 小的数。

符合条件的数如:1, 2, 3, 4, 5, 6, 8, 9, 10, 12...

样例:

如果 n = 9, 返回 10

思路分析:

这类题目就是找规律,找到规律就好写了。

我再提供多一些数据:[1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24]

代码模板:

/**
 * @param n: An integer
 * @return: the nth prime number as description.
 */
const nthUglyNumber = function(n) {
  // write your code here
};
1
2
3
4
5
6
7

想一想再看答案

想一想再看答案

想一想再看答案

代码:

// [1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24]
const nthUglyNumber = function(n) {
  let arr = [1];
  let min,
    nex2,
    nex3,
    nex5,
    i2 = i3 = i5 = 0;
  for (let i = 1; i < n; i++) {
    // 除了第一个数,每个数都是2、3、5的倍数,把它们的倍数找出来,数字较小添加进去
    nex2 = arr[i2] * 2;
    nex3 = arr[i3] * 3;
    nex5 = arr[i5] * 5;
    min = Math.min(nex2, nex3, nex5);
    // 增加他们的倍数 为下次计算做准备
    if (min === nex2) i2++;
    if (min == nex3) i3++;
    if (min == nex5) i5++;
    arr.push(min);
  }
  return arr[arr.length - 1];
  // return arr
};
console.log('输出', nthUglyNumber(9), nthUglyNumber(15));
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

鼓励我一下:

觉得还不错的话,给我的项目点个star

Last Updated: 11/11/2018, 3:48:07 PM