LeetCode 264 Ugly Number II

Posted on | In | 阅读

每一个Ugly Number必定由之前的某一Ugly Number （除了1之外）乘以2，3，5得到。用三个指针分别指向当前x2 x3 x5还没有放进队列的最小数，然后每次从三个数分别x2 x3 x5后取最小值作为新的加入队列的数，并且检查更新三个指针的指。

C++ Code

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
class Solution {
public:
    int min3(int a, int b, int c) {
        if(a < b) {
            if(a < c) return a;
            else return c;
        }else {
            if(b < c) return b;
            else return c;
        }
    }
    
    int nthUglyNumber(int n) {
        int *arr = new int[n];
        arr[0] = 1;
        int k = 1;
        int index2 = 0, index3 = 0, index5 = 0;
        while(k < n) {
            arr[k] = min3(arr[index2] * 2, arr[index3] * 3, arr[index5] * 5);
            if(arr[k] == arr[index2] * 2)
                ++index2;
            if(arr[k] == arr[index3] * 3)
                ++index3;
            if(arr[k] == arr[index5] * 5)
                ++index5;
            ++k;
        }
        int ans = arr[k-1];
        delete [] arr;
        return ans;
    }
};