[Leetcode] Sqrt 开方

BlackFlagBin 发布于2019-08-14 12:25 / 3324人阅读

摘要：二分搜索复杂度时间因为整数长度有限空间思路我们知道必定存在这么两个整数和，所以我们要做的其实就是缩小这个的范围。代码牛顿迭代法复杂度时间空间思路更好的解法是用数学方法，牛顿法是非常经典的求解方程的方法。

Sqrt

Implement int sqrt(int x).
Compute and return the square root of x.

二分搜索 复杂度

时间 O(1) 因为整数长度有限空间 O(1)

思路

我们知道必定存在这么两个整数a和b,a^2 <= sqrt(x) <= b^2，所以我们要做的其实就是缩小这个ab的范围。使用二分法解这题时，通过比较mid^2和x大小来确定我们在哪一个半片中搜索。

注意

这题的边界条件较多，首先high要用long型存储，其次如果有必要的话要判断x是否是非负数。

代码

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

牛顿迭代法 复杂度

时间 O(1) 空间 O(1)

思路

更好的解法是用数学方法，牛顿法是非常经典的求解方程的方法。其基本公式是$$ x_{2}=x_{1}-frac{x_{1}^2-n}{2x_{1}} $$，其中x1是上次计算结果，x2是本次计算结果，当他的误差小于一定值时返回。初始x值可选n/2，或者神奇数0x5f37642f。

代码

public class Solution {
    public int sqrt(int x) {
        // 如果初始值取0x5f37642f，则会进一步加快计算速度
        double x1 = x/2.0;
        double x2 = 0.0, err = x2 - x1;
        while(Math.abs(err)>0.00000001){
            x2 = x1 - (x1 * x1 - x) / (2 * x1);
            err = x2 - x1;
            x1 = x2;
        }
        return (int)x2;
    }
}

GPU云服务器云服务器 Sqrt LeetCode linux 开方 python计算开方

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64460.html

LeetCode69. Sqrt(x) -- 求一个数的开方

摘要：牛顿迭代法的原理很简单，其实是根据在附近的值和斜率，估计和轴的交点，因此牛顿迭代法的公式为其实就是求切线与轴的交点。代码利用牛顿法进行的更新，比直接从开始遍历所作的循环要少牛顿迭代法的基本原理，请参考牛顿迭代法求开平方描述 Implement int sqrt(int x). Compute and return the square root of x, where x is gu...

ddongjian0000 2019-07-30 16:55 评论0 收藏0
[LeetCode] Count Primes

摘要：用数组标记非质数，每当出现一个为，计数器加一。关于质数有三点大于的质数一定是奇数，如，，奇数中的非质数也一定是奇数的乘积。首先，我们用从到进行标记。标记完所有的合数之后，再用到之间的遍历，所有未被标记的质数。 Problem Count the number of prime numbers less than a non-negative number, n. Note 用数组fla...

Shisui 2019-08-14 15:54 评论0 收藏0
《十万字Java入门练习100例》1-10例——纸上得来终觉浅,绝知此事要躬行

摘要：代码实现在控制台打印总结本篇文章带大家搭好环境，并体验了控制台打印。输出结果总结熟练掌握取余和整除运算，大有作用。终止本次循环，继续执行下一次循环。 ?本文收录...

keithyau 2021-10-09 09:44 评论0 收藏0
Emscripten教程之连接C++和JavaScript（三）

摘要：用具体的参数和返回值调用一个编译的函数，而是一个编译的函数的包裹，调用它会返回一个可以调用的函数。如果返回值是或你要指定不同宏，是还是。返回值用于传给数据。对库文件的限制调用函数作为中的函数指针使用返回一个整数来表示一个函数指针。翻译：云荒杯倾本文是Emscripten-WebAssembly专栏系列文章之一，更多文章请查看专栏。也可以去作者的博客阅读文章。欢迎加入Wasm和emsc...

gyl_coder 2019-08-22 11:10 评论0 收藏0