leetcode 264. Ugly Number II

超、凢脫俗 2022-07-26 00:15 156阅读 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.

class Solution {
    	struct Node
    	{
    		int val;
    		vector<int>bb;
    		Node(int x) :val(x){
    			bb.push_back(5);
    			bb.push_back(3);
    			bb.push_back(2);
    		}
    	};
    public:
    	int nthUglyNumber(int n) {
    		clock_t start, finish;
    		double Total_time;
    		start = clock();
    		if (n == 1)
    			return 1;
    		vector<int>cc;
    		cc.push_back(1);
    		vector<Node>candi;
    		candi.push_back(Node(1));
    		while (cc.size() != n)
    		{
    			int min = 2147483647;
    			int ii = -1;
    			int i = 0;
    			while (candi.size() > i)
    			{
    				while (candi[i].val*candi[i].bb.back() <= cc.back())
    					candi[i].bb.pop_back();
    				if (candi[i].val*candi[i].bb.back() < min)
    				{
    					min = candi[i].val*candi[i].bb.back();
    					ii = i;
    				}
    				i++;
    				if (i < candi.size() && candi[i].bb.size() == 3 && candi[i].val * 2 >= min)
    					break;
    			}
    			cc.push_back(min);
    			candi.push_back(Node(min));
    			candi[ii].bb.pop_back();
    			if (candi[ii].bb.empty())
    				candi.erase(candi.begin() + ii, candi.begin() + ii + 1);
    
    		}
    		finish = clock();
    		Total_time = (double)(finish - start) / CLOCKS_PER_SEC;
    		printf("%f seconds\n", Total_time);
    		return cc.back();
    	}
    };

这个超时了，想了想性能的瓶颈可能是每次找min时计算太多，其实上次算出来的结果可以存下来，这样可能会减少一些计算。

改进之后accept

class Solution {
    public:
    	int nthUglyNumber(int n) {
    		clock_t start, finish;
    		double Total_time;
    		start = clock();
    		if (n == 1)
    			return 1;
    		vector<int>cc;
    		cc.push_back(1);
    		set<int>m2, m3, m5;
    		m2.insert(1);
    		m3.insert(1);
    		m5.insert(1);
    		while (cc.size() != n)
    		{
    			while (*m2.begin() * 2 <= cc.back())
    				m2.erase(m2.begin());
    			int a2 = *m2.begin() * 2;
    			while (*m3.begin() * 3 <= cc.back())
    				m3.erase(m3.begin());
    			int a3 = *m3.begin() * 3;
    			while (*m5.begin() * 5 <= cc.back())
    				m5.erase(m5.begin());
    			int a5 = *m5.begin() * 5;
    			int min = a2 < a3 ? a2 : a3;
    			min = min < a5 ? min : a5;
    			if (min == a2)
    				m2.erase(m2.begin());
    			if (min==a3)
    				m3.erase(m3.begin());
    			if (min==a5)
    				m5.erase(m5.begin());
    			m2.insert(min);
    			m3.insert(min);
    			m5.insert(min);
    			cc.push_back(min);
    		}
    
    		finish = clock();
    		Total_time = (double)(finish - start) / CLOCKS_PER_SEC;
    		printf("%f seconds\n", Total_time);
    		return cc.back();
    	}
    };