69. x 的平方根

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 进行换底，即可得到

这样我们就可以得到 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;
    }
1
2
3
4
5
6
7

复杂度分析：

• 时间复杂度：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;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

复杂度分析：

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

方法三：牛顿迭代

牛顿迭代法是一种可以用来快速求解函数零点的方法。
为了叙述方便，我们用 C表示待求出平方根的那个整数。显然，C 的平方根就是函数
的零点。
下图给出了从 x0开始迭代两次，得到 x1和 x2 的过程。

代码：

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;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

复杂度分析：

• 时间复杂度：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;
    }

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

注：仅供学习参考

来源：力扣