Coding LeetCode

LeetCode 69. Sqrt(x)

查阅更多的题解,请点击

Problem

Solution

这道题本身很简单,不过有数学上非常优美的解法,值得一提:Newton’s method

\sqrt{n}的结果满足等式x^2-n=0,该等式的解可以由下述迭代过程得到: x_{k+1}=\frac{(x_k+n/x_k)}{2}, k\geq0,x_0>0 该过程可以证明是一定能收敛到\sqrt{n}的,且当初始猜测为x_0=n时,有较快的收敛速度。

注意迭代过程中x_k的值可能比n要大,所以代码中用了long

GitHub传送门

class Solution
{
  public:
    int mySqrt(int x)
    {
        long r = x;
        while (r * r > x)
            r = (r + x / r) / 2;
        return r;
    }
};

发表评论

电子邮件地址不会被公开。 必填项已用*标注