leetcode:69. x 的平方根

简介: 利用二分查找思想,在0与x区间进行查找。 设置左边界 left (初始值为0),右边界 right(初始值为x)和中值 mid (值为区间的中间值),同时设置一个ans(初始值为-1)作为最终返回值。

一、题目

45b3d44f8c3235f25514188343c386b4_200c4334cf684732921b10e67b963c19.png

函数原型:int mySqrt(int x)


二、思路


       利用二分查找思想,在0与x区间进行查找。


       设置左边界 left (初始值为0),右边界 right(初始值为x)和中值 mid (值为区间的中间值),同时设置一个ans(初始值为-1)作为最终返回值。


       设置循环,循环条件为 left<=right。每次进入循环,通过中值mid的平方与x进行比较确定x的平方根在中值左区间还是右区间或是mid即为x的平方根。mid平方小于x则说明平方根在中值左区间,大于x则说明平方根在中值右区间。


       每次进入循环,先更新一下mid的值,然后再进行比较判断确定平方根所在区间。将平方根在左区间和平方根刚好等于mid的情况合并。如果平方根在左区间或平方根刚好等于mid,则更新区间并将mid的值赋值给ans;如果平方根在右区间,则只更新区间。


最终循环结束后,返回ans。


关键1:中值mid值如何求?


mid = left +(right - left)/ 2


关键2:为什么循环条件是 left<=right ?


只有当left <= right 时,才能保证要求的平方根在区间内。left = right 时也算一个区间,只不过该区间只有一个值。


关键3:为什么只有当mid的平方小于等于x时才将mid的值赋给ans?


当mid的平方等于x时,将mid的值赋给ans毋庸置疑。当mid的平方小于x时,将mid的值赋给ans,是因为在循环中可能会出现所求平方根的精确值在两个相邻整数之间,此时mid的值时较小的整数,我们要求的粗略值也是较小的整数,因此mid的值就是我们要求的ans值。


关键4:为什么mid的平方需要强制类型转换?


因为题目提示部分显示x<=2^31-1,数据较大,int类型可能能存放不下,需要用long long类型存储。

int mySqrt(int x) 
{
  int left = 0;
  int right = x;
  int mid = left + (right - left) / 2;
  int ans = -1;
  while (left <= right)
  {
    mid = left + (right - left) / 2;
    if ((long long)mid * mid <= x )
    {
      left = mid + 1;
      ans = mid;
    }
    else if ((long long)mid * mid > x )
    {
      right = mid - 1;
    }
  }
  return ans;
}


目录
相关文章
|
3月前
|
算法 Java
LeetCode第69题x 的平方根
这篇文章是关于LeetCode第69题"x的平方根"的解题分享。作者介绍了使用二分查找算法来解决这个问题的方法,这是一种简单且有效的方式,可以显著降低求解平方根的时间复杂度。文章提供了详细的分析、解题思路和Java语言的代码实现,最后总结了二分查找思想在算法中的应用价值。
LeetCode第69题x 的平方根
|
3月前
|
算法 Java 索引
LeetCode初级算法题:寻找数组的中心索引+x的平方根+三个数的最大乘积+Leetcode 149:直线上最多的点数 Java详解
LeetCode初级算法题:寻找数组的中心索引+x的平方根+三个数的最大乘积+Leetcode 149:直线上最多的点数 Java详解
36 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)
40 1
|
5月前
|
算法
【经典LeetCode算法题目专栏分类】【第6期】二分查找系列:x的平方根、有效完全平方数、搜索二位矩阵、寻找旋转排序数组最小值
【经典LeetCode算法题目专栏分类】【第6期】二分查找系列:x的平方根、有效完全平方数、搜索二位矩阵、寻找旋转排序数组最小值
【Leetcode-67. 二进制求和-69.x的平方根】
【Leetcode-67. 二进制求和-69.x的平方根】
50 0
|
6月前
【力扣】69. x 的平方根
【力扣】69. x 的平方根
|
6月前
leetcode-69:x 的平方根
leetcode-69:x 的平方根
62 0
YI
|
Go
LeetCode 0069. X的平方根【Go】
LeetCode 0069. X的平方根【Go】
YI
89 0
|
Java Python
leetcode.69:x的平方根
leetcode.69:x的平方根
80 0