• Leetcode(69)——x 的平方根


    Leetcode(69)——x 的平方根

    题目

    给你一个非负整数 x ,计算并返回 x 的 算术平方根

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

    注意:不允许使用任何内置指数函数和算符,例如 pow(x, 0.5) 或者 x ** 0.5

    示例 1:

    输入:x = 4
    输出:2

    示例 2:

    输入:x = 8
    输出:2
    解释:8 的算术平方根是 2.82842…, 由于返回类型是整数,小数部分将被舍去。

    提示:

    • 0 0 0 <= x <= 2 31 − 1 2^{31 - 1} 2311

    题解

    方法一:暴力破解

    思路

    ​​  因为 x x x 的算术平方根向下取整的值一定在 [ 0 , x ] [0, x] [0,x] 中,所以直接暴力地从 0 0 0 遍历到 x x x,直到找到第一个平方大于 x x x 的值,它减去 1 1 1 就是我们要找到的值。

    代码实现

    我自己的:

    class Solution {
    public:
        int mySqrt(int x) {
            long n;
            for(n = 0; n*n <= x; n++);
            return n-1;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    复杂度分析

    时间复杂度 O ( x ) O(x) O(x),最坏情况是从 0 0 0 查找到 x x x 才找到
    空间复杂度 O ( 1 ) O(1) O(1)

    方法二:二分查找

    思路

    ​​  由于 x x x 平方根的整数部分 ans \textit{ans} ans满足 k 2 ≤ x k^2 \leq x k2x 的最大 k k k,因此我们可以对 k k k 进行二分查找,从而得到答案。

    ​​  二分查找的下界为 0 0 0,上界可以粗略地设定为 x x x。在二分查找的每一步中,我们只需要比较中间元素 mid \textit{mid} mid 的平方与 x x x 的大小关系,并通过比较的结果调整上下界的范围。由于我们所有的运算都是整数运算,不会存在误差,因此在得到最终的答案 ans \textit{ans} ans 后,也就不需要再去尝试 ans + 1 \textit{ans} + 1 ans+1 了。

    代码实现

    Leetcode 官方题解:

    class Solution {
    public:
        int mySqrt(int x) {
            int l = 0, r = x, ans = -1;
            while (l <= r) {
                int mid = l + (r - l) / 2;
                if ((long long)mid * mid <= x) {
                    ans = mid;
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
            return ans;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    我的:

    class Solution {
    public:
        int mySqrt(int x) {
            long min = 0, max = x, mid;
            while(min <= max){
                mid = (min + max)/2;
                if(mid*mid < x){
                    if((mid+1)*(mid+1) > x) break;
                    else min = mid+1;
                }else if(mid*mid > x) max = mid-1;
                else break;
            }
            return mid;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    复杂度分析

    时间复杂度 O ( l o g x ) O(logx) O(logx),即为二分查找需要的次数。
    空间复杂度 O ( 1 ) O(1) O(1)

    方法三:牛顿迭代法

    思路

    ​​  牛顿迭代法是一种可以用来快速求解函数零点的方法。

    为了叙述方便,我们用 C C C 表示待求出平方根的那个整数。显然, C C C 的平方根就是函数
    y = f ( x ) = x 2 − C y = f(x) = x^2 - C y=f(x)=x2C

    的零点。

    ​​  牛顿迭代法的本质是借助泰勒级数,从初始值开始快速向零点逼近。我们任取一个 x 0 x_0 x0 作为初始值,在每一步的迭代中,我们找到函数图像上的点 ( x i , f ( x i ) ) (x_i, f(x_i)) (xi,f(xi)),过该点作一条斜率为该点导数 f ′ ( x i ) f'(x_i) f(xi) 的直线,与横轴的交点记为 x i + 1 x_{i+1} xi+1 x i + 1 x_{i+1} xi+1 相较于 x i x_i xi 而言距离零点更近。在经过多次迭代后,我们就可以得到一个距离零点非常接近的交点。下图给出了从 x 0 x_0 x0 开始迭代两次,得到 x 1 x_1 x1 x 2 x_2 x2 的过程。

    在这里插入图片描述

    算法

    我们选择 x 0 = C x_0 = C x0=C 作为初始值。

    在每一步迭代中,我们通过当前的交点 x i x_i xi,找到函数图像上的点 ( x i , x i 2 − C ) (x_i, x_i^2 - C) (xi,xi2C),作一条斜率为 f ′ ( x i ) = 2 x i f'(x_i) = 2x_i f(xi)=2xi 的直线,直线的方程为:
    y l = 2 x i ( x − x i ) + x i 2 − C = 2 x i x − ( x i 2 + C )

    yl=2xi(xxi)+xi2C=2xix(xi2+C)
    yl=2xi(xxi)+xi2C=2xix(xi2+C)

    与横轴的交点为方程 2 x i x − ( x i 2 + C ) = 0 2x_ix - (x_i^2 + C) = 0 2xix(xi2+C)=0 的解,即为新的迭代结果 x i + 1 x_{i+1} xi+1
    x i + 1 = 1 2 ( x i + C x i ) x_{i+1} = \frac{1}{2}\left(x_i + \frac{C}{x_i}\right) xi+1=21(xi+xiC)

    在进行 k k k 次迭代后, x k x_k xk 的值与真实的零点 C \sqrt{C} C 足够接近,即可作为答案。

    细节

    • 为什么选择 x 0 = C x_0 = C x0=C 作为初始值?

    ​​  因为 y = x 2 − C y = x^2 - C y=x2C 有两个零点 − C -\sqrt{C} C C \sqrt{C} C 。如果我们取的初始值较小,可能会迭代到 − C -\sqrt{C} C 这个零点,而我们希望找到的是 C \sqrt{C} C 这个零点。因此选择 x 0 = C x_0 = C x0=C 作为初始值,每次迭代均有 x i + 1 < x i x_{i+1} < x_i xi+1<xi,零点 C \sqrt{C} C 在其左侧,所以我们一定会迭代到这个零点。

    • 迭代到何时才算结束?

    ​​  每一次迭代后,我们都会距离零点更进一步,所以当相邻两次迭代得到的交点非常接近时,我们就可以断定,此时的结果已经足够我们得到答案了。一般来说,可以判断相邻两次迭代的结果的差值是否小于一个极小的非负数 ϵ \epsilon ϵ,其中 ϵ \epsilon ϵ 一般可以取 1 0 − 6 10^{-6} 106 1 0 − 7 10^{-7} 107

    • 如何通过迭代得到的近似零点得出最终的答案?

    ​​  由于 y = f ( x ) y = f(x) y=f(x) [ C , + ∞ ] [\sqrt{C}, +\infty] [C ,+] 上是凸函数(convex function)且恒大于等于零,那么只要我们选取的初始值 x 0 x_0 x0 大于等于 C \sqrt{C} C ,每次迭代得到的结果 x i x_i xi 都会恒大于等于 C \sqrt{C} C 。因此只要 ϵ \epsilon ϵ 选择地足够小,最终的结果 x k x_k xk 只会稍稍大于真正的零点 C \sqrt{C} C 。在题目给出的 32 位整数范围内,不会出现下面的情况:

    真正的零点为 n − 1 / 2 ϵ n−1/2\epsilon n1/2ϵ,其中 n n n 是一个正整数,而我们迭代得到的结果为 n + 1 / 2 ϵ n+1/2\epsilon n+1/2ϵ。在对结果保留整数部分后得到 n n n,但正确的结果为 n − 1 n - 1 n1

    代码实现

    Leetcode 官方题解:

    class Solution {
    public:
        int mySqrt(int x) {
            long ans = x;
            while(ans * ans > x)
                ans = (ans + x/ans)/2;
            return ans;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    复杂度分析

    时间复杂度 O ( log ⁡ x ) O(\log x) O(logx),此方法是二次收敛的,相较于二分查找更快。
    空间复杂度 O ( 1 ) O(1) O(1)

    方法四:袖珍计算器算法

    思路

    ​​  「袖珍计算器算法」是一种用指数函数 exp ⁡ \exp exp 和对数函数 ln ⁡ \ln ln 代替平方根函数的方法。我们通过有限的可以使用的数学函数,得到我们想要计算的结果。

    我们将 x \sqrt{x} x 写成幂的形式 x 1 / 2 x^{1/2} x1/2,再使用自然对数 e e e 进行换底,即可得到
    x = x 1 / 2 = ( e ln ⁡ x ) 1 / 2 = e 1 2 ln ⁡ x \sqrt{x} = x^{1/2} = (e ^ {\ln x})^{1/2} = e^{\frac{1}{2} \ln x} x =x1/2=(elnx)1/2=e21lnx

    这样我们就可以得到 x \sqrt{x} x 的值了。

    ​​  注意: 由于计算机无法存储浮点数的精确值(浮点数的存储方法可以参考 IEEE 754,这里不再赘述),而指数函数和对数函数的参数和返回值均为浮点数,因此运算过程中会存在误差。例如当 x = 2147395600x=2147395600 时, e 1 2 ln ⁡ x e^{\frac{1}{2} \ln x} e21lnx 的计算结果与正确值 4634046340 相差 1 0 − 11 10^{-11} 1011,这样在对结果取整数部分时,会得到 4633946339 这个错误的结果。

    ​​  因此在得到结果的整数部分 ans \textit{ans} ans 后,我们应当找出 ans \textit{ans} ans ans + 1 \textit{ans} + 1 ans+1 中哪一个是真正的答案。

    代码实现

    Leetcode 官方题解:

    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
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    复杂度分析

    时间复杂度 O ( 1 ) O(1) O(1),由于内置的 exp 函数与 log 函数一般都很快,我们在这里将其复杂度视为 O ( 1 ) O(1) O(1)
    空间复杂度 O ( 1 ) O(1) O(1)

  • 相关阅读:
    jvm attach实现一种简单更新rancher上测试环境代码的方法
    js获取当前时间
    向量数据库技术全景
    C++面向对象程序设计(第2版)第二章(类和对象的特性)知识点总结
    少儿编程 电子学会图形化编程等级考试Scratch一级真题解析(选择题)2022年9月
    医学影像特征提取与导出
    计算机毕业设计springboot+vue+elementUI进销存管理信息系统
    VUE day_07(7.25)学子商城项目简略版
    芯片制造:一颗芯片到底是如何诞生的(下)
    uniapp中 background-image 设置背景图片不展示问题
  • 原文地址:https://blog.csdn.net/KCDCY/article/details/125554123