【力扣】69. x 的平方根

文章目录

求开方

69. x 的平方根

题目描述:

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根,其中 x 是非负整数。

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

示例 1:

输入: 4
输出: 2

示例 2:

输入: 8
输出: 2

说明:

8 的平方根是 2.82842…,
由于返回类型是整数,小数部分将被舍去。

Math工具类计算

我们知道 java 的工具类中有计算平方根的方法,我们直接用就可以了。

代码:

 public int mySqrt(int x) {
         double sqrt = Math.sqrt(x);
        return (int)sqrt;
    }

执行用时:1 ms,

内存消耗:35.3 MB

二分查找

我们可以用二分查找来定位平方根的位置,一个数的平方根不会超过它的一半,所以 (x/2)2 <= x,得 x<=4。当 x = 3,时,返回 1 =3/2,当 x = 4时,返回,2 = 4/2。所以只需对x =0 和 x=1 做单独判断。

注意:

  1. 使用mid > x/mid 作为判断条件 而不用 mid * mid > x 是因为如果 mid 很大,那么有可能会超出整形范围。
  2. 在区间只有2个数的时候,有 mid =left ,一旦进入[mid …right],则区间不会继续在缩小,导致死循环。整数除法的下取整行为,导致了区间划分是 [left…mid - 1] 与 [mid…right] 的时候,如果搜索进入区间 [mid…right] 的时候,left = mid 导致区间不再缩小,进入死循环。

一开始我看此题时也是陷入了死循环中,看力扣中liweiwei1419的解题思路也算是成功解出

代码:

  static int mySqrt(int x) {
        /*
         *1. 定义左右区间,左边设置为0,右边为a
         * 2. 判断 mid 和 左右区间的关系
         */

        if (x == 0 || x == 1) {
            return x;
        }
        int l = 1, r = x;
        while (l < r) {
            //上取整防止进入死循环
            int mid = l + (r-l+1) / 2 ;

            if ( x / mid== mid) {
                return mid;
            } else if (x / mid > mid) {
                l = mid ;
            } else {
                r = mid - 1;
            }
        }

        return l;
    }

牛顿迭代法

参考链接:https://leetcode-cn.com/problems/sqrtx/solution/niu-dun-die-dai-fa-by-loafer/

上一篇:大数据之Hive:Hive 开窗函数(一)


下一篇:69. x 的平方根(leetcode)