x 的平方根

发表于 | 分类于 |
字数统计: 1.1k 字 | 阅读时长 ≈ 4 分钟

题目描述：实现 int sqrt(int x) 函数。

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

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

示例 1:
输入: 4
输出: 2

示例 2:
输入: 8
输出: 2
说明: 8 的平方根是 2.82842…,
由于返回类型是整数，小数部分将被舍去。

方法一：二分查找法

由于非负整数 x（当 x ≠ 0 时） 的平方根一定是落在区间 [1, x/2 + 1]，所以左右边界分别取 1 和 x/2 + 1，而不分别取 0 和 x，这样可缩小查找范围。

为了防止 mid * mid 太大而发生整型溢出，取 mid 跟 x/mid 比较。

说明

右边界 right 取 x/2 + 1，而不取 x/2，这是因为当 x = 1 时，right 如果取 x/2，由于 x/2 会向下取整使得 x/2 = 0，此时 left = 1 大于 right = 0，以至于直接跳出循环，导致 1 的平方根为 0，这明显是错误的。

当 x = 0 时，以下代码也适合。

补充说明

如果没有出现 mid == x / mid 的情况，最后到底是 return right 还是 return left？

  1. 可以通过调试得出；
  2. 循环结束的条件是 left = right + 1，示例中提示了当 x = 8，其平方根是 2，有点类似于向下取整的意思，所以是 return right 。
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
class Solution {
  public int mySqrt(int x) {
    int i = 1, j = x / 2 + 1;
    //  循环不变量  始终维持在区间 [left, right] 中查找，当 left = right + 1 时，区间为空，查找结束
    //  当 left == right 时，区间 [left, right] 依然有效 
    while (i <= j) {
      //  防止溢出
      int mid = i + (j - i) / 2;
      if (x / mid == mid) {
        return mid;
      } else if(x / mid < mid) {
        j = mid - 1;
      } else {
        i = mid + 1;
      }
    }
    return j;
  }
}
var mySqrt = function(x) {
    let i = 1, j = Math.floor(x / 2 + 1)
    //  循环不变量  始终维持在区间 [left, right] 中查找，当 left = right + 1 时，区间为空，查找结束
    //  当 left == right 时，区间 [left, right] 依然有效 
    while(i <= j) {
        let mid = Math.floor(i + (j - i) / 2)
        if(x / mid === mid) {
            return mid
        } else if(x / mid < mid) {
            j = mid - 1
        } else {
            i = mid + 1
        }
    }
    return j
};

复杂度分析

  • 时间复杂度：O(logx)，即为二分查找需要的次数。
  • 空间复杂度：O(1)。

执行结果：通过

  • 执行用时：2 ms, 在所有 Java 提交中击败了45.78%的用户
  • 内存消耗：35.7 MB, 在所有 Java 提交中击败了21.41%的用户

方法二：牛顿迭代

迭代的方法是用泰勒级数近似

记住牛顿法的公式：xi = 0.5 * (x0 + C / x0) ，反复迭代到x0 与 xi 相差的绝对值小于1e-7即可

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
class Solution {
  public int mySqrt(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;
  }
}

var mySqrt = function(x) {
    if(x === 0) return 0

    let x0 = x, C = x
    while(true) {
        let xi = 0.5 * (x0 + C / x0)
        // 如果题目要求精确到xxx小数，控制右边的数值即可 
        if(Math.abs(Math.floor(x0) - Math.floor(xi)) < 1e-7) {
            break
        }
        x0 = xi
    }
    return Math.floor(x0)
};

复杂度分析

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

执行结果：通过

  • 执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户
  • 内存消耗：35.6 MB, 在所有 Java 提交中击败了20.45%的用户

变形：精确到xxx小数

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
// import java.text.DecimalFormat; 
class Solution {
  public int mySqrt(int x) {
    if (x == 0) {
      return 0;
    }

    // double C = x, x0 = x;
    float C = x, x0 = x;
    while (true) {
      // double xi = 0.5 * (x0 + C / x0);
      float xi = (float)0.5 * (x0 + C / x0);
      if (Math.abs(x0 - xi) <= 1e-6) { // 精确到 0.000001 
        break;
      }
      x0 = xi;
    }
    // DecimalFormat df = new DecimalFormat("#.000000");
    // System.out.println(df.format(x0));
    // System.out.println(x0);
    System.out.println(x0);
    return (int) x0;
  }
}

// 输入 8
// 2.828427
// 2.8284271250498643

var mySqrt = function(x) {
    if(x === 0) return 0

    let x0 = x, C = x
    while(true) {
        let xi = 0.5 * (x0 + C / x0)
        if(Math.abs(Math.floor(x0) - Math.floor(xi)) < 1e-6) {
            break
        }
        x0 = xi
    }
  	console.log(Math.floor(x0))
    return Math.floor(x0)
};