面试热题（x的平方根）

系统管理员 2023-10-14 13:57 3阅读 0赞

> 给你一个非负整数 `x` ，计算并返回 `x` 的 **算术平方根** 。
> 
> 由于返回类型是整数，结果只保留 **整数部分** ，小数部分将被 **舍去 。**
> 
> **注意：**不允许使用任何内置指数函数和算符，例如 `pow(x, 0.5)` 或者 `x ** 0.5` 。

这道题虽然是简单题，可它表现的也不是那么简单，刚看到题的时候，我也想的是用内置函数，可是正当我写的时候，看到了题目的要求(可我还是用)

return (int)Math.pow(x,0.5);

我又拿了其他方式写了几次，现在给大家分享一下我的做题思路

第一种方式（找区间）：

我们可以假设为该区间是由红绿颜色组成的，红色代表的是小于等于目标值，绿色代表大于目标值，这样：

![8b7369645f9b634dbaaf3dbd64989068.png][]

通过不断的移动，指针终会从红色变为绿色，我们求的目标值就是红色区域的最后一个元素

//利用二分查找进行求解
        public int mySqrt(int x) {
         if(x==0||x==1){
             return x;
         }
         int r=find(x,0,x);
         return r-1;
    
        }
    
        public boolean isGree(int val,int x){
            return (long)val*val>x;
        }
        public int find(int x,int left,int right){
          if(left>right){
              return 0;
          }
          //找到最右侧的第一个红色
          while(left<right){
              int mid=left+(right-left)/2;
              if(isGree(mid,x)){
                  right=mid;
              }else{
                  left=mid+1;
              }
          }
          return left;
        }

方法二（普通的二分搜索）

public int mySqrt(int x) {
          if(x==0||x==1){
              return x;
          }
          int left=0;
          int  right=x;
          while(left<=right){
              int mid=left+(right-left)/2;
              if(mid==x/mid){
                  return mid;
              }else if(mid<x/mid){
                   left=mid+1;
              }else{
                  right=mid-1;
              }
          }
          return right;
        }

方法三（最右侧的二分搜索）：

这种方法我觉的你学会了你才是对二分搜索有了一定的理解，它的取值范围还是它的边界初始值，因为这种靠左侧靠右侧的方法训话条件都是left<right,而不是left等于right,因为题目中给定的参数根号x是可以取到的，所以我们为了凑写个条件写成right=x+1，这样就可以套我们的模板了，具体模板看[一起学算法（二分搜索篇）][Link 1]

public int mySqrt(int x) {
          if(x==0||x==1){
              return x;
          }
          int left=0;
          int  right=x+1;
          while(left<right){
              int mid=left+(right-left)/2;
              if(mid<=x/mid){
                   left=mid+1;
              }else{
                  right=mid;
              }
          }
          return left-1;
        }

模板就套好了，当我提交的时候，错了！！！

![114244f83e5b4a0c8d0e3b86c04e4961.png][]

最后几个居然过不去，遇到这种情况过不去，千万别回头检查代码的问题，过了90%多的代码一般不会出现什么大的问题，我建议的方法是直接打表

if(x==2147483647){
              return 46340;
          }

然后过了，这种直接打表的方式还是很好用的，效率也嘎嘎高！！！

[8b7369645f9b634dbaaf3dbd64989068.png]: https://img-blog.csdnimg.cn/img_convert/8b7369645f9b634dbaaf3dbd64989068.png
[Link 1]: https://blog.csdn.net/dfdbb6b/article/details/132021061?spm=1001.2014.3001.5501
[114244f83e5b4a0c8d0e3b86c04e4961.png]: https://img-blog.csdnimg.cn/114244f83e5b4a0c8d0e3b86c04e4961.png