Leetcode 69. x 的平方根

Offer 驾到，掘友接招！我正在参与2022春招打卡活动，点击查看活动详情。

1、题目?

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

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

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

实例1：

输入：x = 4

输出：2

实例2：

输入：x = 8

输出：2

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

限制：

0 <= x <= 231 - 1

2、思路?

方法一：二分法

从题目的要求和示例我们可以看出，是一个查找整数的问题，且这个整数是有范围的。

整数的平方等于输入整数，找到了这个整数；
整数的平方大于输入整数，这个整数一定不是我们要找的那个数，需要找的数一定在这个数字的前面。
整数的平方小于输入整数，这个整数可能是我们要找的那个数。

一定要理清楚程序的逻辑，确定程序最后指针指向的位置。

方法二：牛顿迭代法

属于是一种迭代的求解过程，即利用递归来求解。证明过程如下图

我们求解得到一个公式：(x + a / x) / 2 a是需要求解算术平方根的数字，是个定值 x 是我们需要求解的零点的值

废话少说~~~~~上代码！

3、代码?‍?

第一次commit AC

class Solution {
    public int mySqrt(int x) {
        if(x == 0) return 0;
        if(x == 1) return 1;
        int R = x;
        int L = 0;
        while(L <= R) {
            int M = L + ((R-L) >> 1);
            if(M > (long)x / M){
                //L...M-1
                R = M - 1;
            }else{
                //M....R
                L = M + 1;
            }
        }
        return R;
    }
}
复制代码

时间复杂度：O(log N) 每一次搜索的区间大小约为原来的二分之一

空间复杂度：O(1)

第二次commit AC

class Solution {
    int a;
    public int mySqrt(int x) {
        a = x;
        if(x == 0) return 0;
        if(x == 1) return 1;
        double result = (x + a / x) >> 1;
        double x1 = x;
        while(true){
            result = (x1 + a / x1) / 2;
            if(result == x1){
                break;
            }
            x1 = result;
        }
        return (int) result;
    }
}
复制代码

时间复杂度：O(log N) 此方法是收敛的，相较于二分查找更快。

空间复杂度：O(1)

4、总结

该题目的使用二分查找的应用实例，首先要对二分法有所了解。

二分法模板：

public static int binarysearch(int arr[], int L, int R, int target){
    int count = 0;
    int M = (L + R) >> 1;
    if(L > R) return -1;

    if (target > arr[M]){
        return binarysearch(arr, M + 1, R, target);
    }else if(target < arr[M]){
        return binarysearch(arr, L, M - 1, target);
    }else {
        return M;
    }
}
复制代码