69. x 的平方根

r囧r小猫 2024-04-01 15:44 204阅读 0赞

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

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

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

注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x \*\* 0.5 。

##### 示例 1： #####

> 输入：x = 4  
> 输出：2

##### 示例 2： #####

> 输入：x = 8  
> 输出：2  
> 解释：8 的算术平方根是 2.82842…, 由于返回类型是整数，小数部分将被舍去。

##### 提示： #####

0 <= x <= 2 ^ 31 - 1

### 题解： ###

#### 方法一：袖珍计算器算法 ####

「袖珍计算器算法」是一种用指数函数 exp 和对数函数 ln代替平方根函数的方法。我们通过有限的可以使用的数学函数，得到我们想要计算的结果。  
我们将 x 写成幂的形式 x^1/2，再使用自然对数 e 进行换底，即可得到  
![在这里插入图片描述][cd03f33ef1d543cfbe0a77a77d437a54.png]  
这样我们就可以得到 x的值了。

##### 代码： #####

public static int mySqrt(int x) {
        //法一：袖珍计算器算法
            if (x == 0) {
        
                return 0;
            }
            int ans = (int) Math.exp(0.5 * Math.log(x));
            return (long) (ans + 1) * (ans + 1) <= x ? ans + 1 : ans;
        }

##### 复杂度分析： #####

*  时间复杂度：O(1)
 *  空间复杂度：O(1)

#### 方法二：二分查找 ####

由于 x 平方根的整数部分 ans 是满足 k^2≤x的最大 k 值，因此我们可以对 k 进行二分查找，从而得到答案。  
二分查找的下界为 0，上界可以粗略地设定为 x。在二分查找的每一步中，我们只需要比较中间元素 m 的平方与 x 的大小关系，并通过比较的结果调整上下界的范围。

> 注：由于m\*m有可能数太大，所以采用相除的方法：

##### 代码： #####

public static  int mySqrt1(int x) {
        //法二：二分查找
    		if(x == 0 || x == 1) 
    			return x;
    		int l = 0, h = x;
    		while(l < h) {
        
    			int m = l + (h - l) / 2;
    			if(x/m < m) {
        
    				h = m-1;
    			}else if(m * m <= x && x/(m+1)<(m+1)){
        
    				return m;
    			}else {
        
    				l = m + 1;
    				
    			}
    		}
    		return l;
        }

##### 复杂度分析： #####

*  时间复杂度：O(log(x)),即为二分查找需要的次数
 *  空间复杂度：O(1)

#### 方法三：牛顿迭代 ####

牛顿迭代法是一种可以用来快速求解函数零点的方法。  
为了叙述方便，我们用 C表示待求出平方根的那个整数。显然，C 的平方根就是函数  
![在这里插入图片描述][c9a9b08f560c4a1398c0cd946c92892f.png]的零点。  
下图给出了从 x0开始迭代两次，得到 x1和 x2 的过程。  
![在这里插入图片描述][e76c3155e9e94f0e8d246ab8fa874c60.png]  
![在这里插入图片描述][47a7480a1ba54e169f391fa8573677c8.png]

##### 代码： #####

public static int mySqrt2(int x) {
        //法三：牛顿迭代
            if (x == 0) {
        
                return 0;
            }
    
            double C = x, x0 = x;
            while (true) {
        
                double xi = 0.5 * (x0 + C / x0);
                if (Math.abs(x0 - xi) < 1e-7) {
        
                    break;
                }
                x0 = xi;
            }
            return (int) x0;
        }

##### 复杂度分析： #####

*  时间复杂度：O(log(x)),此方法是二次收敛的，相较于二分查找更快。
 *  空间复杂度：O(1)

### 所有代码： ###

public class bi_sqrt {
        
    
    	public static void main(String[] args) {
        
    		// TODO 自动生成的方法存根
    		int x = 2147395601;
    		System.out.println(mySqrt1(x));
    //		System.out.println(46340*46340);
    	}
    	public static int mySqrt(int x) {
        //法一：袖珍计算器算法
            if (x == 0) {
        
                return 0;
            }
            int ans = (int) Math.exp(0.5 * Math.log(x));
            return (long) (ans + 1) * (ans + 1) <= x ? ans + 1 : ans;
        }
    
    	public static  int mySqrt1(int x) {
        //法二：二分查找
    		if(x == 0 || x == 1) 
    			return x;
    		int l = 0, h = x;
    		while(l < h) {
        
    			int m = l + (h - l) / 2;
    			if(x/m < m) {
        
    				h = m-1;
    			}else if(m * m <= x && x/(m+1)<(m+1)){
        
    				return m;
    			}else {
        
    				l = m + 1;
    				
    			}
    		}
    		return l;
        }
    	public static int mySqrt2(int x) {
        //法三：牛顿迭代
            if (x == 0) {
        
                return 0;
            }
    
            double C = x, x0 = x;
            while (true) {
        
                double xi = 0.5 * (x0 + C / x0);
                if (Math.abs(x0 - xi) < 1e-7) {
        
                    break;
                }
                x0 = xi;
            }
            return (int) x0;
        }
    
    }

##### 注：仅供学习参考 #####

来源：[力扣][Link 1]

[cd03f33ef1d543cfbe0a77a77d437a54.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/296ef88b8532464eb9a49da3839738fa.png
[c9a9b08f560c4a1398c0cd946c92892f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/062d1f23be364c639bfec9902e86859c.png
[e76c3155e9e94f0e8d246ab8fa874c60.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/272728525cf446c5859b1c538106fb47.png
[47a7480a1ba54e169f391fa8573677c8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/8f3d0574370e4edb9123d27f645a5494.png
[Link 1]: https://leetcode.cn/problems/sqrtx/description/