69. x 的平方根

查看题目

简单

算法

中频

解法一：二分查找

时间复杂度：O(log x) | 空间复杂度：O(1) | 推荐使用

动画演示

输入值 x:

准备就绪 - 输入一个非负整数，然后点击开始

代码实现


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

时间复杂度：O(log x)

空间复杂度：O(1)

使用二分查找算法在 [0, x] 区间内查找平方根的整数部分。

解法二：迭代法

时间复杂度：O(log x) | 空间复杂度：O(1)

动画演示

输入值 x:

准备就绪 - 输入一个非负整数，然后点击开始

代码实现


class Solution {
    public int mySqrt(int x) {
        if (x == 0) {
            return 0;
        }

        double C = x, x0 = x;
        while (true) {
            double xi = 0.5 * (x0 + C / x0);
            if (Math.abs(x0 - xi) < 1e-7) {
                break;
            }
            x0 = xi;
        }
        return (int) x0;
    }
}

时间复杂度：O(log x)

空间复杂度：O(1)

使用牛顿迭代法不断逼近平方根的近似解，直到误差小于阈值。

解法三：数学

时间复杂度：O(1) | 空间复杂度：O(1)

动画演示

输入值 x:

准备就绪 - 输入一个非负整数，然后点击开始

代码实现


class Solution {
    public int mySqrt(int x) {
        if (x == 0) {
            return 0;
        }
        int ans = (int) Math.exp(0.5 * Math.log(x));
        return (long) (ans + 1) * (ans + 1) <= x ? ans + 1 : ans;
    }
}

时间复杂度：O(1)

空间复杂度：O(1)

使用数学公式 exp(0.5 * log(x)) 计算平方根，然后进行边界检查。