网络异常,图片无法展示
|
「这是我参与2022首次更文挑战的第26天,活动详情查看:2022首次更文挑战」
给你一个非负整数 x
,计算并返回 x
的 算术平方根 。
由于返回类型是整数,结果只保留 整数部分 ,小数部分将被 舍去 。
注意: 不允许使用任何内置指数函数和算符,例如 pow(x, 0.5)
或者 x ** 0.5
。
示例 1:
输入: x = 4 输出: 2 复制代码
示例 2:
输入: x = 8 输出: 2 解释: 8 的算术平方根是 2.82842..., 由于返回类型是整数,小数部分将被舍去。 复制代码
提示:
0 <= x <= 231 - 1
解题思路
因为本题不允许使用指数函数的算符,所以我们没有办法通过将 x
开发然后对结果向下取整的方式解题。
这里我们转换一下思路,我们可以找到第一个平方后的结果大于 x
的整数,而它 -1
就是本题要求的算术平方根。
而且基于数学知识,我们知道,一个非负整数的算术平方根必然是大于等于 0
而且小于等于它自己的,所以本题的结果必然是在 0~x
之间。
又因为从 0~x
之间的整数是单调递增的,所以我们可以利用二分查找第一个平方结果大于 x
的数字,而目标值就是该数字 -1
。
这里有一个需要注意的点是当 x = 0
或者 x = 1
时,无法通过二分查找获取正确的结果。
以 x = 1
为例,第一次查找之后虽然 mid*mid<=x
,但是因为 l=r
,所以二分查找会结束,此时 l = r = 1
,返回 -1
后的结果为 0
,所以我们要对 1
进行特殊判断,当 x = 1
时,直接返回 1
即可。
代码实现
var mySqrt = function(x) { // 特殊判断 0 和 1 if(x===0 || x===1) return x; // 因为已经特判了 0 1,所以左边界设置为1,右边界为 x let l = 1,r = x; // 二分查找第一个平方结果大于 x 的整数 while(l<r){ const mid = Math.floor((l+r)/2); if(mid*mid<=x) l = mid+1 else r = mid; } // 返回该数字-1的结果,即为 x 的算术平方根 return l-1; }; 复制代码
至此我们就完成了 **leetcode-69-x 的平方根 **
如有任何问题或建议,欢迎留言讨论!👏🏻👏🏻👏🏻