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