美文网首页
求算术平方根

求算术平方根

作者: 沉默的小象 | 来源:发表于2023-07-02 11:01 被阅读0次

leetcode 69题
求x的算术平方根。例如4的算术平方根是2。 8的算术平方根也是2(取整)。9的算术平方根是3。

注意的点

  • 使用二分查找法,(递归和while循环)
  • 二分查找是先比较mid与目标值的大小,而不是先比较两端left和right。
  • 节省内存:少新建变量
  • 节省内存:用窄类型,例如用byte替换int。
  • 减少执行用时:优化算法。

递归实现

public class Test {
    public static void main(String[] args) {
        System.out.println(mySqrt(2));
        System.out.println(mySqrt(3));
        int x = 2147483647;
        System.out.println(mySqrt(x));
    }

    public static int mySqrt(int x) {
        if (x == 0) {
            return 0;
        }
        if (x == 1) {
            return 1;
        }
        return count(1, x, x);
    }

    public static int count(int left, int right, int x) {
//      System.out.println("start:" + left + " " + right);
        int mid = left + (right - left) / 2; //防止(left+right)溢出

        if (mid == x / mid) {//防止溢出用除法
            return mid;
        } else if (mid < x / mid) {//mid*mid<x
            if ((mid + 1) > x / (mid + 1)) { //(mid+1)*(mid+1)>x
                return mid;
            } else {
                return count(mid + 1, right, x);
            }
        } else if (mid > x / mid) {//mid*mid>x
            return count(left, mid - 1, x);
        }
        System.out.println("error");
        return -1;
    }

}

while循环实现

public class Test2 {
    public static void main(String[] args) {
        System.out.println(mySqrt(2));
        System.out.println(mySqrt(8));
//        System.out.println(mySqrt(2147483647));

    }

    public static int mySqrt(int x) {
        // 特殊值判断
        if (x == 0) {
            return 0;
        }
        if (x == 1) {
            return 1;
        }

        int left = 1;
        int right = x;
        // 在区间 [left..right] 查找目标元素
        while (left <= right) {
            int mid = left + (right - left) / 2;
//            System.out.println("开始:left:" + left + " right:" + right + " mid:" + mid);
            if (mid > x / mid) { // 注意:这里为了避免乘法溢出,改用除法
                right = mid - 1; // 下一轮搜索区间是 [left..mid - 1]
            } else if (mid == x / mid) {
                return mid;
            } else {
                // 下一轮搜索区间是 [mid+1..right]
                left = mid + 1;
            }
//            System.out.println("结束:left:" + left + " right:" + right);
        }
        return left - 1;
    }

}

相关文章

网友评论

      本文标题:求算术平方根

      本文链接:https://www.haomeiwen.com/subject/olnzydtx.html