69.Sqrt(x)

以你之姓@ 2022-08-28 11:56 122阅读 0赞

题目描述：

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。由于返回类型是整数，结果只保留整数部分，小数部分将被舍去 。

示例：

输入：x = 8
    输出：2
    解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。

解题方法：二分法。直接先上代码：

public class MySqrt {
    
        public static int mySqrt(int x) {
            if (x < 2) {
                return x;
            }
            int left = 1;
            int right = x / 2;
            while (left <= right) {
                int middle = left + (right - left) / 2;
                System.out.println("left = " + left + ", right = " + right + ", middle = " + middle);
                // 使用 middle * middle 会溢出，所以改使用除法
                if (x / middle > middle) {
                    // middle * middle < x
                    left = middle + 1;
                } else if (x / middle < middle) {
                    // middle * middle > x
                    right = middle - 1;
                } else {
                    return middle;
                }
            }
            return right;
        }
    
        public static void main(String[] args) {
            long startTime = System.currentTimeMillis();
            int x = 1000;
            int result = mySqrt(x);
            System.out.println("result = " + result);
            long endTime = System.currentTimeMillis();
            System.out.println("程序运行时间：" + (endTime - startTime) + "ms");
        }
    
    }

使用变量 left、right、middle 来进行处理。我们先处理 x = 0 和 x = 1 的情况，之后才算正式进入二分法处理。初始化 left = 1，right = x / 2，意味着最终的结果会在 1 ~ x / 2 的范围中产生，middle = （left + right）/ 2。然后去循环进行 middle \* middle 与 x 的比较，如果 middle \* middle > x，则说明结果会在 \[left, middle) 范围内产生，然后给 right 赋值 middle -1，然后重新计算 middle 值，重新进行比较；如果 middle \* middle < x，则说明结果会在 (middle, right\] 范围内产生，然后给 left 赋值 middle + 1，然后重新计算 middle，重新进行比较；如果 middle \* middle == x，则直接返回 middle 即可。如果对 x 处理完了之后也没有找到可以返回的 middle 值，则直接返回 right 即可，比如，当 x = 6 时，进行 2 次处理后各个值的情况为：left = 3, right = 2, middle = 3，此时并没有找到可直接返回的 middle 值，继续执行时发现循环条件已经不满足了，所以直接返回 right 即可。

除了二分法之外，还有一种投机取巧的方法。

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