[路飞]_leetcode-69-x 的平方根

简介: leetcode-69-x 的平方根

网络异常,图片无法展示
|


「这是我参与2022首次更文挑战的第26天,活动详情查看:2022首次更文挑战


[题目地址][B站地址]


给你一个非负整数 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 的平方根 **


如有任何问题或建议,欢迎留言讨论!👏🏻👏🏻👏🏻

相关文章
|
3月前
|
算法 Java
LeetCode第69题x 的平方根
这篇文章是关于LeetCode第69题"x的平方根"的解题分享。作者介绍了使用二分查找算法来解决这个问题的方法,这是一种简单且有效的方式,可以显著降低求解平方根的时间复杂度。文章提供了详细的分析、解题思路和Java语言的代码实现,最后总结了二分查找思想在算法中的应用价值。
LeetCode第69题x 的平方根
|
3月前
|
算法 Java 索引
LeetCode初级算法题:寻找数组的中心索引+x的平方根+三个数的最大乘积+Leetcode 149:直线上最多的点数 Java详解
LeetCode初级算法题:寻找数组的中心索引+x的平方根+三个数的最大乘积+Leetcode 149:直线上最多的点数 Java详解
35 0
|
5月前
|
SQL 算法 数据可视化
leetcode题目69:x的平方根【python】
leetcode题目69:x的平方根【python】
leetcode题目69:x的平方根【python】
|
5月前
|
算法 Java Go
【经典算法】LeetCode 69. x 的平方根(Java/C/Python3/Golang实现含注释说明,Easy)
【经典算法】LeetCode 69. x 的平方根(Java/C/Python3/Golang实现含注释说明,Easy)
36 1
|
5月前
|
算法
【经典LeetCode算法题目专栏分类】【第6期】二分查找系列:x的平方根、有效完全平方数、搜索二位矩阵、寻找旋转排序数组最小值
【经典LeetCode算法题目专栏分类】【第6期】二分查找系列:x的平方根、有效完全平方数、搜索二位矩阵、寻找旋转排序数组最小值
【Leetcode-67. 二进制求和-69.x的平方根】
【Leetcode-67. 二进制求和-69.x的平方根】
45 0
|
6月前
【力扣】69. x 的平方根
【力扣】69. x 的平方根
|
6月前
leetcode-69:x 的平方根
leetcode-69:x 的平方根
60 0
|
存储
leetcode:69. x 的平方根
利用二分查找思想,在0与x区间进行查找。 设置左边界 left (初始值为0),右边界 right(初始值为x)和中值 mid (值为区间的中间值),同时设置一个ans(初始值为-1)作为最终返回值。
96 0
YI
|
Go
LeetCode 0069. X的平方根【Go】
LeetCode 0069. X的平方根【Go】
YI
89 0