题目链接

LeetCode

题目描述

实现 int sqrt(int x) 函数。

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

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

示例 1:

输入: 4
输出: 2

示例 2:

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

解题思路

方法一：二分查找

  1. class Solution {
  2. public:
  3.     int mySqrt(int x) {
  4.         // 右边为x/2+1，减少循环
  5.         int l = 0, r = x/2+1, ans = -1;
  6.         while (l <= r) {
  7.             int mid = l + (r - l) / 2;
  8.             // 强制类型转换，截取long long部分数据
  9.             if ((long long)c * mid <= x) {
  10.                 ans = mid;
  11.                 l = mid + 1;
  12.             } else {
  13.                 r = mid - 1;
  14.             }
  15.         }
  16.         return ans;
  17.     }
  18. };
  • 时间复杂度 O(log n)
  • 空间复杂度 O(1)

    方法二：牛顿迭代法

    牛顿迭代法是一个可以求一个任意函数的零点的工具。它比二分法快得多。
    求x的平方根相当于求f(x) = x^2 - C为0时的x，进而转为求零点问题。

69. x 的平方根* - 图1
image.pngimage.png
绝对值小于1e-7视为等于0

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 (fabs(x0 - xi) < 1e-7) {
                break;
            }
            x0 = xi;
        }
        return int(x0);
    }
};
  • 时间复杂度 O(log n) 比二分查找更快。
  • 空间复杂度 O(1)