【刷题-LeetCode】264. Ugly Number II

Ugly Number II

Write a program to find the n-th ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.

Example:

Input: n = 10

Output: 12

Explanation: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.

Note:

1 is typically treated as an ugly number.
n does not exceed 1690.

解法1

暴力搜索。假设已经知道了前n个丑数\(a_1, a_2, ..., a_n\)，求第n+1个丑数，则有：

\[a_{n+1} = \min\{2*a_i, 3*a_j, 5*a_k\}, \quad \forall i, j, k\in[1, n]\\
s.t\quad a_{n+1} > a_n
\]

class Solution {

public:

    int nthUglyNumber(int n) {

        vector<int>u_n{1};

        int prime[3] = {2, 3, 5};

        while(u_n.size() < n){

            int flag = 0;

            int cur_n = INT_MAX;

            for(int i = u_n.size() - 1; i >= 0; --i){

                for(int j = 0; j < 3; ++j){

                    if(u_n[i]*prime[j] > u_n.back()){

                        cur_n = min(cur_n, u_n[i]*prime[j]);

                    }else{

                        flag++;

                    }

                }

                if(flag == 3)break;

            }

            u_n.push_back(cur_n);

        }

        return u_n.back();

    }

};

但是提交会超时。。。

解法2 对解法1进行改进。显然丑数数组是有序的，可以用二分查找完成，查找的问题描述为：

寻找第一次出现的满足 \(k\times a_i > a_n\)的\(a_i\)

搜索过程为：对于区间\([l, r]\)

\(k\times a_{mid} > a_n\)，则满足条件的肯定在\([l, mid]\)中
\(k\times a_{mid} \leq a_n\)，则满足条件的肯定在\([mid+1, r]\)中

typedef long long int LL;

class Solution {

public:

    int nthUglyNumber(int n) {

        vector<LL>u_n{1};

        int prime[3] = {2, 3, 5};

        while(u_n.size() < n){

            LL cur_n = LLONG_MAX;

            for(int j = 0; j < 3; ++j){

                int idx = bin_search(u_n, prime[j]);

                cur_n = min(cur_n, prime[j]*u_n[idx]);

            }

            u_n.push_back(cur_n);

        }

        return u_n.back();

    }

    int bin_search(vector<LL>&nums, int k){

        int last_num = nums.back();

        int l = 0, r = nums.size()-1;

        while(l < r){

            int mid = (l + r) / 2;

            if(nums[mid]*k > last_num)r=mid;

            else l = mid + 1;

        }

        return l;

    }

};

解法3 注意到事实：如果\(a_n\)是丑数，则\(2a_n, 3a_n, 5a_n\)也是丑数

typedef long long int LL;

class Solution {

public:

    int nthUglyNumber(int n) {

        priority_queue<LL, vector<LL>, greater<LL>>q;

        set<LL>s;

        int prime[3] = {2, 3, 5};

        q.push(1);

        s.insert(1);

        LL ans = q.top();

        for(int i = 0; i < n; ++i){

            ans = q.top();

            q.pop();

            s.erase(ans);

            for(int j = 0; j < 3; ++j){

                if(s.find(ans*prime[j]) == s.end()){

                    q.push(ans*prime[j]);

                    s.insert(ans*prime[j]);

                }

            }

        }

        return ans;

    }

};

解法4 根据解法三种事实，利用动态规划

class Solution {

public:

    int nthUglyNumber(int n) {

        int pre2 = 0, pre3 = 0, pre5 = 0;

        int nums[1690];

        nums[0] = 1;

        for(int i = 1; i < n; ++i){

            int ugly = min(nums[pre2]*2, min(nums[pre3]*3, nums[pre5]*5));

            nums[i] = ugly;

            if(ugly % 2 == 0)pre2++;

            if(ugly % 3 == 0)pre3++;

            if(ugly % 5 == 0)pre5++;

        }

        return nums[n-1];

    }

};

巴特西

【刷题-LeetCode】264. Ugly Number II

最新文章

热门文章