题目

题解

1. 二分查找法

  • 时间复杂度$o(log{N})$
  • 空间复杂度$O(1)$
class Solution {
public:
    int mySqrt(int x) {//两个方法。1、二分查找法
        if (x <= 1) return x;//0和1直接返回
        int left = 0, right = x;//这里直接用x就行，每次是取一半，用x问题不大
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (x / mid >= mid) left = mid + 1;//注意1：使用x/mid >= mid来判断，而不是mid*mid >= mid
            else right = mid;//注意2：left是mid+1，right是mid
        }
        return right - 1;//注意3：返回right-1
    }
};

2. 牛顿迭代法

  • 时间复杂度$o(log{N})$
  • 空间复杂度$O(1)$ 牛顿法的主要递推公式是$x_{n+1} = x_{n}-\frac{f(x_{n})}{f^{'}(x_{n})}$，递推到和0差的值很小即可停止。
class Solution {
public:
    int mySqrt(int x) {//两个方法。2、牛顿迭代法
        if(x<=1) return x;
        double res = x/2;//随机取一个数作为第一个数，取x/2
        while(abs(res*res-x) > 1e-6){//定义一个阈值，小于阈值停止迭代
            res = (res + x/res)/2;//这个参考牛顿法公式
        }
        return res;
    }
};