LeetCode 未知数的平方根使用JavaScript解题|前端学算法

2023-01-07 128

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： LeetCode 未知数的平方根使用JavaScript解题|前端学算法

x 的平方根

给你一个非负整数 x ，计算并返回 x 的算术平方根。由于返回类型是整数，结果只保留整数部分，小数部分将被舍去。

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

示例 1：

输入：x = 4

输出：2

示例 2：

输入：x = 8

输出：2

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

解题思路

可以从1开始挨个平方，看看那个值的平方与x最为接近，但是这是方式太麻烦了，及其浪费性能和耗费时间。可以使用二分法，我们知道平方根的整数部分是<= x/2的,所以我们在这个范围内做二分查找，找到某个数的平方为x即可

具体步骤如下：

第一步：如果X小于2时直接返回X
第二步：初始化二分法的左右指针，left为1；right为x/2的整数部分
第三步：当左指针小于等于右指针时进入循环：

二分法计算出中间值 mid
如果mid的平方等于x就返回mid
如果mid的平方小于x就令左指针等于mid+1,否则就令右指针为mid-1

第四步：返回 right

var mySqrt = function(x) {
    if(x < 2) return x;
    let left = 1;
    let right = Math.floor(x / 2);
    while(left <= right) {
        let mid = Math.floor(left + (right - left) / 2);
        if(mid * mid === x) return mid;
        if(mid * mid < x){
             left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return right;
};