概要

难度：简单

类型：每日一题

题目

实现 int sqrt(int x) 函数。

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

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

示例

示例 1:

输入: 4
输出: 2
示例 2:

输入: 8
输出: 2
说明: 8 的平方根是 2.82842..., 
     由于返回类型是整数，小数部分将被舍去。

来源：力扣（LeetCode）
链接：https:///problems/sqrtx
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

分析

第一种思路，暴力破解。

第二种思路，是看题解想出来的思路，但是最后处理2147395599这个数的时候超时了，自己的编译器会得出结果，但是提交给LeetCode会超时，其实还是暴力破解。

第三种思路就是官方题解，也就是二分法。

代码

第一种思路

    /**
     * 求x的平方根（第一种算法：暴力破解）
     * @param x
     * @return
     */
    public int mySqrt(int x) {
        int k = 1;
        while (x / k >= k) {
            k++;
        }
        return k - 1;
    }

第二种思路

    /**
     * 求x的平方根
     * @param x
     * @return
     */
    public long mySqrt(int x){
        if(x==0){
            return (int)x;
        }
        if(x==1){
            return (int)x;
        }
        long low=0;
        long high=x;
        long mid=-1;
        while (low<high){
            mid=(high-low)/2;
            if(mid*mid<=x){
                return (int)mid;
            }else if(mid*mid>x){
                high-=1;
            }
        }
        return (int)mid;
    }

第三种思路

    public int mySqrt(int x){
        int low = 0, high = x, ans = -1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if ((long)mid * mid <= x) {
                ans = mid;
                low = mid + 1;
            }
            else {
                high = mid - 1;
            }
        }
        return ans;
    }