Leetcode69. x 的平方根_69ⅹⅹ

Leetcode69. x 的平方根

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

• 时间复杂度：$O(logN)$，二分法的时间复杂度是对数级别的。
• 空间复杂度：$O(1)$，使用了常数个数的辅助空间用于存储和比较。

 def mySqrt(x: Int): Int = {

    var left: Long = 0l
    var right: Long = x / 2 + 1l

    while (left < right) {
      // 注意：这里一定取右中位数，如果取左中位数，代码可能会进入死循环
      val mid: Long = left + (right - left + 1)  / 2
      val square = mid * mid
      if (square > x) {
        right = mid - 1
      } else {
        left = mid
      }
    }
    left.toInt
  }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

方法二：牛顿法

牛顿法原理：是不断运用$(x,f(x))$的切线与$x$轴的焦点来逼近方程$x^2-a=0$的根。
函数$f(x)=x^2-a$在$(x_0,f(x_0))$处的切线方程为：$f(x)-f(x_0)=f^{\prime }(x_0)(x-x_0)$
切线方程和$x$轴的交点：
令$f(x)=0$得：$f(x_0)+(x-x_0)f^{\prime }(x_0)=0$
$$x=x_0-\frac{f(x_0)}{f^{\prime }(x_0)}=x_0-\frac{x_0^2-a}{2x_0}=\frac{2x_0^2-x_0^2+a}{2x_0}=\frac{1}{2}(x_0+\frac{a}{x_0})$$

故迭代公式：$x=\frac{1}{2}(x_0+\frac{a}{x_0})$

java代码：

 public static int mySqrt(int a) {
        if (a == 0) return 0;
        int x = a;
        while (x * x > a) {
            x = (x + a / x) / 2;
        }
        return x;
    }
1
2
3
4
5
6
7
8

def mySqrt2(a: Int): Int = {
    var x = 0l
    if (a == 0) {
      x = 0l
    } else {
      x = a.toLong
      while (x * x > a) {
        x = (x + a / x) / 2
      }
    }
    x.toInt
  }
1
2
3
4
5
6
7
8
9
10
11
12