leetcode-236-Ugly Number

2019-11-08 02:31:48

字体：大中小

来源：转载

供稿：网友

问题

题目：[leetcode-236]

思路

素数筛法的思路。但是第一遍TLE。仔细想了下，这个两边循环的代码时间是没有问题的，因为之前的帖子也学习了。不是完全的O(N2) $O(N^{2})$ 的复杂度。

所以，考虑整数的最大值2147483647。500002>INTMAX $50000^{2} > INTMAX$ 。所以，我猜测可能是辅助空间开大了。因为之前看的和num一样大，那么当num给INT_MAX的时候，时间就上去了。这么分析之后，修改了代码，正确。

所以，改bug是件很重要的事情。根据错误，快速定位，猜测可能出现错误的地方，进行修改就行。原则，只要有一丝希望，就要去尝试。

两个注意点：

辅助空间大小的开辟（n√ $/sqrt{n}$ ）大素因子的判断(只能有一个大于n√ $/sqrt{n}$ 的因子)，对本体来说，只要出现返回false.

代码

class Solution {public: bool isUgly(int num) { if(1==num) return true; else if(num < 1) return false; else{ const int maxn = 50000; vector<int> PRime_table; vector<bool> marker(maxn+1, 0); for(int i = 2; i <=maxn; ++i){ if(marker[i]) continue; else{ prime_table.push_back(i); for(int j = i*2; j <= maxn; j += i){ marker[j] = true; } } } int prime_cnt = prime_table.size(); int index = 0; while( num != 1 && index < prime_cnt ){ int& prime = prime_table[index]; while( num != 1 && num % prime == 0 ){ num /= prime; if(prime>5) return false; } index++; } if(num != 1) return false; else return true; } }};

上一篇：蓝桥杯 ALGO-115 算法训练和为T

下一篇：Layout POJ - 3169（差分约束）题解