正文索引 [隐藏]

传送门→

据说是高频面试题。

大意是不用sqrt去实现开平方根计算，小数向下取整。

pow做法

第一想法是用pow函数，众所周知开平方＝½次方：

class Solution {
public:
    int mySqrt(int x) {
        int ans = pow(x, 1.0/2);
        return ans;
    }
};

过是过了，但是时间复杂度很高，仅击败36%。于是开始学习更先进的算法。

对数做法

还有一种算法是利用自然对数的换底公式来计算。

[latexpage]
\sqrt{x} = x^ \frac{1}{2} = e^ \ln x \frac{1}{2} 

class Solution {
public:
    int mySqrt(int x) {
        if (x == 0) return 0;
        int ans = exp(0.5 * log(x));
        return ((long long)(ans + 1) * (ans + 1) <= x ? ans + 1 : ans);
    }
};

看了LC官方的解答，有这么一段：

注意： 由于计算机无法存储浮点数的精确值（浮点数的存储方法可以参考 IEEE 754，这里不再赘述），而指数函数和对数函数的参数和返回值均为浮点数，因此运算过程中会存在误差。例如当 x=2147395600 时，计算结果与正确值 46340 相差 10^-11，这样在对结果取整数部分时，会得到 46339这个错误的结果。
因此在得到结果的整数部分 ans 后，我们应当找出 ans 与 ans+1 中哪一个是真正的答案。

所以才会有那一句条件语句。