C++面試題目
判斷一個自然數是否是某個數(自然數)的平方。
要求:不能用開方函數。
解決方案
思路一:
遍歷1到n,將每個數的平方與n比較,若小於則遞增;若等於則返回;若大於,則失敗。
時間複雜度:sqrt(n)
思路二:
二分查找1到n中某個數的平方為n,時間複雜度為logn.
思路三:
根據等差數列公式:1+3+5+7+……+(2n-1) = n^2,所以任意數的平方都能用一個初值為1,等差為2的等差數列表示,所以判斷一個數是不是平方數可以用這個數不斷的減2,如果最後減到為0,那麼這個數就是平方數,否則不是。
時間複雜度sqrt(n)。
閱讀更多 半杯茶的小酒杯 的文章