给你一个非负整数 x ,计算并返回 x 的 算术平方根 。由于返回类型是整数,结果只保留 整数部分 ,小数部分将被 舍去 。注意:不允许使用任何内置指数函数和算符,例如 pow(x, 0.5)
1.暴力解法--袖珍计算器 class Solution { public: int mySqrt(int x) { int y=exp(0.5*log(x)); if((y+1)*(y+1)>=x) return (y+1); else return y; } }; 复杂度分析 时间复杂度:O(1),由于内置的 exp 函数与 log 函数一般都很快,我们在这里将其复杂度视为 O(1) 空…