x的平方根几种解法

x的平方根

题目地址：  https://leetcode-cn.com/problems/sqrtx/

题目描述：

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。

注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

示例

输入： x = 4
输出： 2

输入： x = 8
输出： 2
解释： 8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。

题目分析

本题难度较低，在leetcode上属于简单类型的题目，不过这里有一个不允许使用内置函数和算符，不然直接使用parentInt(Math.sqrt(x))即可求得结果。

一般在面试时，面试官给出算法题，除非遇到过，并且非常熟悉，基本第一时间可能都会想到暴力求解的方式。然后解出来之后，面试官可能会问是否有更好的解法，让时间复杂度更低，这时就要看你对算法的真正掌握程度了。（当然对于难度较高的，可能暴力求解才是真的坑）

• 暴力求解

一般来说最符合逻辑的想法就是暴力求解了，那就是一个一个整数乘积计算过去，如果计算到某个整数乘积大于了x，那就回退一位，这样即可得到结果了。

暴力代码：(值得一提的是，暴力求解的代码空间复杂度较为优秀)

var mySqrt = function(x) {
    if (x == 0 | x == 1) return x;
    let res = 0;
    while(res * res <= x) {
        res++;
    }
    return res - 1;
};

• 二分法求解

这是在暴力求解算法的基础上进行演化，每次都取中间的值，在两端可以设立双指针，根据这两根指针来判断中间值。如果中间值乘积大于x，则将右指针修改为中间值-1，否则将res先赋值为中间值，并且左指针修改为中间值+1

二分代码：

var mySqrt = function(x) {
    if (x == 0 | x == 1) return x;
    let res = 0;
    let leftindex = 0, rightindex = x;
    while(leftindex <= rightindex) {
        let mid = parseInt(leftindex + (rightindex - leftindex)/2);
        if (mid * mid <= x) {
            res = mid;
            leftindex = mid + 1;
        } else {
            rightindex = mid - 1;
        }
    }
    return res;
};

• 牛顿迭代

牛顿迭代法是一种可以用来快速求解函数零点的方法

这种方法我是看了题解，但其实也没怎么看明白的，后来看视频看懂的

简单来说，比如求解20的平方根4.47213595499958，20可以由（2 * 10）、（4 * 5）得到，对于（2 * 10）的平均数6， 6比2、10更加接近真正的平方根。同理，（4 * 5）的平均数4.5也比4或5更加接近平方根。

其实最终就是一个递归求解均值的方法

每次的均值都是（x/n + n）/2 = res。 比如（20 / 10 + 10）/2 = 6，然后用6带入n，（20 / 6 + 6）/2 = 4.6667，然后继续代入，（20 / 4.6667 + 4.6667）/2 = 4.4762，此时已经非常接近真正的平方根4.47213595499958了。那么神秘时候停止呢，就是当res与n相等时，结束递归，得到的就是平方根

我看到这个方法时，直呼666，感觉自己被降维打击了一番，算法真的是越学越头秃。

牛顿迭代代码：相较于上面两种，此方法时间复杂度最优

var mySqrt = function(x) {
    if (x == 0 | x == 1) return x;
    // 不断递归寻找均值
    function sqrtFun(i, x) {
        let res = (i + x / i)/2;
        if (res == i) {
            return res
        } else {
            return sqrtFun(res, x);
        }
    }

    let num = sqrtFun(x, x)
    
    return parseInt(num);
};

所以对于这样一道看起来很简单的题目，内涵算法也非常复杂。现在回过头来真的要感谢平时使用的API，像JavaScript中的Math函数，如果没有，真让我们自己去定义，真的会累死人的。