^{<output id="3rbwr"></output>}<style id="3rbwr"><i id="3rbwr"></i></style>

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（差分約束）題解