【力扣】69. x 的平方根

今天药忘吃喽~ 2022-10-08 05:48 10阅读 0赞

### 文章目录 ###

*   *  求开方
     *   *  69. x 的平方根
         *   *  Math工具类计算
             *  二分查找
             *  牛顿迭代法

## 求开方 ##

### 69. x 的平方根 ###

**题目描述：**

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根，其中 x 是非负整数。

由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

**示例 1:**

> 输入: 4  
> 输出: 2

**示例 2:**

> 输入: 8  
> 输出: 2

**说明:**

8 的平方根是 2.82842…,  
由于返回类型是整数，小数部分将被舍去。

#### Math工具类计算 ####

我们知道 java 的工具类中有计算平方根的方法，我们直接用就可以了。

**代码：**

public int mySqrt(int x) {
        
             double sqrt = Math.sqrt(x);
            return (int)sqrt;
        }

执行用时：1 ms,

内存消耗：35.3 MB

#### 二分查找 ####

我们可以用二分查找来定位平方根的位置，一个数的平方根不会超过它的一半，所以 （x/2）2 <= x,得 x<=4。当 x = 3，时，返回 1 =3/2，当 x = 4时，返回，2 = 4/2。所以只需对x =0 和 x=1 做单独判断。

**注意：**

1.  使用mid > x/mid 作为判断条件 而不用 mid \* mid > x 是因为如果 mid 很大，那么有可能会超出整形范围。
2.  在区间只有2个数的时候，有 mid =left ，一旦进入\[mid …right\],则区间不会继续在缩小，导致死循环。整数除法的下取整行为，导致了区间划分是 \[left…mid - 1\] 与 \[mid…right\] 的时候，如果搜索进入区间 \[mid…right\] 的时候，left = mid 导致区间不再缩小，进入死循环。

> 一开始我看此题时也是陷入了死循环中，看力扣中**liweiwei1419**的解题思路也算是成功解出

**代码：**

static int mySqrt(int x) {
        
            /*
             *1. 定义左右区间，左边设置为0，右边为a
             * 2. 判断 mid 和 左右区间的关系
             */
    
            if (x == 0 || x == 1) {
        
                return x;
            }
            int l = 1, r = x;
            while (l < r) {
        
                //上取整防止进入死循环
                int mid = l + (r-l+1) / 2 ;
    
                if ( x / mid== mid) {
        
                    return mid;
                } else if (x / mid > mid) {
        
                    l = mid ;
                } else {
        
                    r = mid - 1;
                }
            }
    
            return l;
        }

#### 牛顿迭代法 ####

参考链接：https://leetcode-cn.com/problems/sqrtx/solution/niu-dun-die-dai-fa-by-loafer/