leetcode 264. Ugly Number II 计算第K个丑数

末蓝、 2022-06-08 13:24 177阅读 0赞

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

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.

Note that 1 is typically treated as an ugly number, and n does not exceed 1690.

题意很简单，上一道题是除法，这一道题是乘法。

建议和上一道题[leetcode 263. Ugly Number][]和 [leetcode 313. Super Ugly Number 超级丑数][leetcode 313. Super Ugly Number]一起学习。

代码如下：

import java.util.SortedSet;
    import java.util.TreeSet;
    
    /*
     * 这个很棒，需要学习
     * 
     * */
    class Solution {
        public int nthUglyNumber(int n) 
        {
            SortedSet<Long> set=new TreeSet<>();
            set.add((long)1);
    
            long one=set.first();
            for(int i=0;i<n;i++)
            {
                one=set.first();
                set.add(one*2);
                set.add(one*3);
                set.add(one*5);
                set.remove(one);
            }
            return (int)(one);
        }
    
    }

下面是C++的做法，上一道题是除法做法，这一道题是乘法做法，设置三个指针即可，代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    
    using namespace std;
    
    
    
    class Solution
    {
    public:
        int nthUglyNumber(int n)
        {
            vector<long long> res;
            set<long long> ss;
            ss.insert(1);
            while (res.size() < n)
            {
                long long a = *(ss.begin());
                ss.insert(a * 2);
                ss.insert(a * 3);
                ss.insert(a * 5);
                ss.erase(a);
                res.push_back(a);
            }
            return res[n - 1];
        }
    
        int nthUglyNumberByCala(int n) 
        {
            vector<int> res(1,1);
            int i = 0, j = 0, k = 0;
            while (res.size() < n)
            {
                int a = min(res[i] * 2, min(res[j] * 3, res[k] * 5));
                res.push_back(a);
                if (a == res[i] * 2)
                    i++;
                if (a == res[j] * 3)
                    j++;
                if (a == res[k] * 5)
                    k++;
            }
            return res[n - 1];
        }
    };

[leetcode 263. Ugly Number]: http://blog.csdn.net/jackzhang_123/article/details/78109379
[leetcode 313. Super Ugly Number]: http://blog.csdn.net/jackzhang_123/article/details/78150024