第n个丑数

前言：

1. 何为丑数？
丑数，就是只含有2、3、5三个因子的正整数。
2. 如何让判断丑数？
一个数先被2整除，直到不能被2整除，再被3整除，直到不能被3整除，再被5整除，直到不能被5整除，除到最后如果只剩下1则为丑数，否则不为丑数
3. 判断丑数代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

#include <iostream>
using namespace std;
class Solution {
public:
    bool isUgly(int num) {
          if (num==0) {
            return false;
        }else if(num==1){
            return true;
        }else{

            int tmp = num;
            while (tmp%2 == 0) {
                tmp = tmp/2;
            }
            while (tmp%3 == 0) {
                tmp = tmp/3;
            }
            while (tmp%5 == 0) {
                tmp = tmp/5;
            }
            if (tmp==1) {
                return true;
            }else{
                return false;
            }

        }
    }
};

问题要求：

例如1, 2, 3, 4, 5, 6, 8, 9, 10, 12 为前10个丑数，求第n个丑数

做法：

1. 我们可以利用队列来帮助我们解决问题，首先我们需要3个队列q2、q3、q5，这三个队列分别存储能被2、3、5整除的整数；
2. 1为第一个丑数，我们用p来记录当前的丑数，求第n个丑数，则循环n-1次以下操作：首先2*p、3*p、5*p分别插入q2、q3、q5队列，取各个队头元素获取他们之中的最小值，该最小值也是该次循环的丑数，再判断各个队头元素是否与这个最小值相等，如果相等则出队，再将该最小值赋值为p；
3. 循环结束，p就是第n个丑数；

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

#include <iostream>
#include <queue>
using namespace std;
class Solution {
public:
    int min1(int a,int b){
        return a<b?a:b;
    }

    int nthUglyNumber(int n) {
        if (n<=0) {
            return -1;
        }else if (n==1) {
            return 1;
        }else{
            queue<int> q2;
            queue<int> q3;
            queue<int> q5;
            int i = 1;
            int p = 1;
            while (i<n) {
                q2.push(p*2);
                q3.push(p*3);
                q5.push(p*5);
                int min2 = q2.front();
                int min3  = q3.front();
                int min5 = q5.front();
                int min = min1(min1(min2, min3), min5);
                if (min2==min) {
                    q2.pop();
                }
                if (min3==min) {
                    q3.pop();
                }
                if (min5==min) {
                    q5.pop();
                }
                p = min;
                i++;
            }
            return p;
        }
    }
};
int main(int argc, const char * argv[]) {
    // insert code here...
    Solution* s = new Solution();
    cout<<s->nthUglyNumber(4)<<endl;
    return 0;
}

Comments