leetcode69x的平方根

约定不等于承诺〃 2022-10-08 13:22 302阅读 0赞

在这里插入图片描述
思路：[l,r];mid=(l+r)/2

  1. 使用temp=x/mid而不是mid*mid来进行比较计算，这样容易超出范围
  2. 二分法查找
    （1）合适的平方根只有在temp>mid的时候出现，比如8/1=8;8/2=4;8/3=2，结果为mid最大值。
    （2）mid的移动方向与temp有关，temp>mid时尽量让mid最大，l=mid+1。temp<mid时mid过大r=mid-1。

代码

  1. int mySqrt(int x){ 
  2.     long r = x;
  3.     long l=1;
  4.     int ans=0;
  5.     if(x==0||x==1)
  6.         return x;
  7.     while (l<=r)
  8.     { 
  9.         long mid = (l+r)/2;
  10.         int temp = x/mid;
  11.         if(temp==mid)
  12.             return mid;
  13.         if(temp>mid){ 
  14.             l=mid+1;
  15.             if(ans < mid)
  16.             ans = mid;
  17.         }
  18.         else{ 
  19.             r=mid-1;
  20.         }   
  21.     }
  22.     return ans;
  23. }

发表评论

表情：
评论列表 （有 0 条评论，302人围观）

还没有评论，来说两句吧...

相关阅读

    相关 leetcode69 x的平方根

    实现 int sqrt(int x) 函数。 计算并返回 x 的平方根，其中 x 是非负整数。 由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。 示例 1:

    朱雀朱雀/ 0 赞/ 245 阅读

    相关 【LeetCode 69】x的平方根

    题目描述 实现 int sqrt(int x) 函数。 计算并返回 x 的平方根，其中 x 是非负整数。 由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

    怼烎@怼烎@/ 0 赞/ 186 阅读