LeetCode算法题-Sqrt(Java实现)

LeetCode算法题-Sqrt(Java实现)

这是悦乐书的第158次更新,第160篇原创

01 看题和准备

今天介绍的是LeetCode算法题中Easy级别的第17题(顺位题号是69)。 计算并返回x的平方根,其中x保证为非负整数。 由于返回类型是整数,因此将截断十进制数字,并仅返回结果的整数部分。例如:

输入:4
输出:2
输入:8
输出:2
说明:8的平方根是2.82842 …,从2以后小数部分被截断,返回2

本次解题使用的开发工具是eclipse,jdk使用的版本是1.8,环境是win7 64位系统,使用Java语言编写和测试。

02 第一种解法

使用二分法来算平方根。

特殊情况一:在求中间数时,需要考虑整型溢出的情况。因为在计算中间数时,习惯性很容易就写出mid = (right+left)/2,但是left+right的值如果溢出,那么整个计算都是失真的。此时,我们就需要做下替换,用减法替代加法:

right/2 + left/2
right/2 - left/2 + left
(right-left)/2 + left

特殊情况二:在判断中间数的平方是否等于传入的参数时,习惯性就写出 mid*mid == x,这其实也是存在溢出风险的,也可以变换下,做除法,即 x/mid == mid。

特殊情况三:传入的参数小于等于0的时候,直接返回0即可。

二分法来取平方根,低位取1,高位是x本身,如果低位小于等于高位,就进入循环求得两者中间数,做除法比较是否相等,相等则返回中间数,如果高位除以中间数大于中间数,则低位等于中间数向前加1,如果高位除以中间数小于中间数,则高位等于中间数向后减1。直到低位大于高位,结束循环,返回高位。

public int mySqrt(int x) {
    if (x < 1)
        return 0;
    int low = 1;
    int high = x;
    while (low <= high) {
        int mid = (high - low) / 2 + low;
        if (x / mid == mid)
            return mid;
        if (x / mid > mid)
            low = mid + 1;
        if (x / mid < mid)
            high = mid - 1;
    }
    return high;
}

03 第二种解法

直接使用Math自身的sqrt()方法,如果面试时遇到此题,还是以上面的解法或者下面的第三种为好。

public int mySqrt2(int x) {
    return (int) Math.sqrt(x);
}

04 第三种解法

利用牛顿迭代法计算开平方根,在此不过多描述,会单独抽时间来写这个经典的求平方根解法。

public int mySqrt3(int x) {
    double flag = 0.1d;
    if (x <= 0) {
        return 0;
    }
    double val = x;
    double last;
    do {
        last = val;
        val = (val + x / val) / 2;
    } while (val - last > flag || val - last < -flag);
    return (int) val;
}

05 测试用例和结果

对比上述三种解法,使用了一些数据做了测试,并记录了算法花费的时间。

public static void main(String[] args) {
    Easy_069_Sqrt instance = new Easy_069_Sqrt();
    int arg = 2;
    long start = System.nanoTime();
    int result = instance.mySqrt(arg);
    long end = System.nanoTime();
    System.out.println("mySqrt()---输入:" + arg + " , 输出:" + result + " , 用时:" + ((end - start) / 1000) + "微秒");
    System.out.println("-----------------------------------------------");
    long start2 = System.nanoTime();
    int result2 = instance.mySqrt2(arg);
    long end2 = System.nanoTime();
    System.out.println("mySqrt2()---输入:" + arg + " , 输出:" + result2 + " , 用时:" + ((end2 - start2) / 1000) + "微秒");
    System.out.println("-----------------------------------------------");
    long start3 = System.nanoTime();
    int result3 = instance.mySqrt3(arg);
    long end3 = System.nanoTime();
    System.out.println("mySqrt3()---输入:" + arg + " , 输出:" + result3 + " , 用时:" + ((end3 - start3) / 1000) + "微秒");
}

测试结果如下

mySqrt()---输入:3600 , 输出:60 , 用时:4微秒
-----------------------------------------------
mySqrt2()---输入:3600 , 输出:60 , 用时:20微秒
-----------------------------------------------
mySqrt3()---输入:3600 , 输出:60 , 用时:5微秒

06 小结

方法1和方法3运算速度还是较快的,Math类的sqrt方法与之对比还是稍逊一些。以上就是全部内容,如果大家有什么好的解法思路、建议或者其他问题,可以下方留言交流,点赞、留言、转发就是对我最大的回报和支持!