0069-x的平方根

题目链接

题目描述

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

示例

示例1：

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

思路

思路1：二分查找

每一步都考虑 mid 的平方与 x 的关系，想象一个由 mid * mid 组成的有序数组 nums，此题其实就可以转换成查找右边界问题。
优化：
考虑将搜索范围由 [0, x] 缩小至 [0, x/2] ，为保证正确性，有 成立，即 ，因此我们要对 进行特判，但其实对于 来说，算法的结果也是正确的。
经过优化，虽然复杂度没有变，但却可以有效降低运行时间。

思路2：牛顿法

牛顿法可以求解方程的近似解，在本题中，我们有 ，方程的零点为 ，因为我们只需要整数，所以可以从 开始迭代。
由迭代公式：
得：

思路3：换底法

我们可以进行如下换底操作：
注：exp() 和 log() 返回值都为浮点数，因此最终计算结果可能会有精度损失，我们需要比较 ans 和 ans + 1 哪个是正确答案。

题解

思路1：二分查找

class Solution {
public:
    int mySqrt(int x) {
        if(1 == x){
            return 1;
        }
        int left = 0, right = x / 2;
        while(left <= right){
            int mid = ((right - left) >> 1) + left;
            if((long long)mid * mid <= x){
                left = mid + 1;            
            }else{
                right = mid - 1;
            }
        }
        return left - 1;
    }
};

思路2：牛顿法

class Solution {
   public:
    int mySqrt(int x) {
        if (x == 0) {
            return 0;
        }

        long i = x;
        while (i * i > x) {
            i = (i + x / i) / 2;
        }

        return (int)i;
    }
};

思路3：换底法

class Solution {
   public:
    int mySqrt(int x) {
        if (x == 0) {
            return 0;
        }
        int ans = exp(0.5 * log(x));
        return ((long long)(ans + 1) * (ans + 1) <= x ? ans + 1 : ans);
    }
};

复杂度分析

思路1：二分查找

• 时间复杂度：

• 空间复杂度：

  思路2：牛顿法

• 时间复杂度：

• 空间复杂度：

  思路3：换底法

• 时间复杂度：，exp() 和 log() 的时间复杂度我们认为是

• 空间复杂度：