LeetCode演算法題-Perfect Number(Java實現)
這是悅樂書的第249 次更新,第262 篇原創
01 看題和準備
今天介紹的是LeetCode演算法題中Easy級別的第116題(順位題號是507)。我們定義Perfect Number是一個正整數,它等於除了它自己之外的所有正除數之和。現在,給定一個整數n,編寫一個函式,當它是一個完美數字時返回true,否則返回false。例如:
輸入:28
輸出:true
說明:28 = 1 + 2 + 4 + 7 + 14
注意:輸入數字n不會超過100,000,000。(1E8)
本次解題使用的開發工具是eclipse,jdk使用的版本是1.8,環境是win7 64位系統,使用Java語言編寫和測試。
02 第一種解法
特殊情況:最小Perfect Number為6,奇數不可能是Perfect Number
正常情況:num對從2開始的正整數做取餘操作,等於0,就表示能夠被整除,將能夠被整除的數累加起來,最後判斷與num是否相等。在迴圈中,我們可以將num除以2再判斷,而不必一直遍歷到num,因為超過num/2的數再乘以另外一個數(1除外)肯定會大於num。
此解法的時間複雜度是O(n),其中n只用判斷n/2次,空間複雜度是O(1)。
public boolean checkPerfectNumber(int num) { if (num < 6 || num%2 != 0) { return false; } int sum = 1; for (int i=2; i<=num/2; i++) { if (num%i == 0) { sum += i; } } return sum == num; }
03 第二種解法
我們是不是可以將for迴圈中的迴圈次數再縮小一點?第一種解法是num/2次,而一個正整數它所包含的因子,兩兩相乘,當兩因子無限逼近的時候,就是正整數的平方根,但是使用平方根作為迴圈次數的上限,會把右邊的因子排除掉,所以我們需要提前就加進去,當num能被當前因子整除時,它的商就是右邊的一個因子,所以需要將兩個因子都加上。最後還是判斷因子之和是否與num相等。
此解法的時間複雜度是O(n),其中n只用判斷根號n次,空間複雜度是O(1)。
public boolean checkPerfectNumber2(int num) { if (num < 6 || num%2 != 0) { return false; } int sum = 1; for (int i=2; i<=Math.sqrt(num); i++) { if (num%i == 0) { sum += i + num/i; } } return sum == num; }
04 第三種解法
最小的Perfect Number是6,接著是28,然後是496
6: 2x3 true
28: 4x7 true
120: 8x15 false
496: 16x31 true
2016: 32x63 false
8128: 64x127 true
上面這些數,可以看做2的(n-1)次方與2的n次方再減1的乘積,其中n從2開始,但是並非所有的n都符合,在上面幾個數中,當n等於4和6時是不符合Perfect Number的,這裡直接給出符合的數吧,2,3,5,7,13,17,19,31,至於17,19,31這幾個次方數,做乘法會溢位,可以直接不考慮,至於為什麼是這幾個數,可以一個一個往下推,不難。當然,你要是把int範圍內的5個Perfect Number(第5個是33550336)都找出來了,直接做判斷也行。
public boolean checkPerfectNumber3(int num) { int[] primes = {2,3,5,7,13}; for (int p: primes) { if ((1 << (p - 1)) * ((1 << p) - 1) == num) { return true; } } return false; }
05 小結
演算法專題目前已日更超過三個月 ,演算法題文章116 +篇,公眾號對話方塊回覆【資料結構與演算法 】、【演算法 】、【資料結構 】中的任一關鍵詞,獲取系列文章合集。
以上就是全部內容,如果大家有什麼好的解法思路、建議或者其他問題,可以下方留言交流,點贊、留言、轉發就是對我最大的回報和支援!