Easy

题目描述

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

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

**注意：**不允许使用任何内置指数函数和算符。

  • 例如，c++ 中的 pow(x, 0.5) 函数，或者 python 中的 x ** 0.5 。

示例 1：

输入：x = 4
输出：2

示例 2：

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

提示：

  • 0 <= x <= 2^31 - 1

解题思路

这道题要求计算平方根并向下取整，有多种解法：

方法一：二分查找（推荐） 由于平方根具有单调性，我们可以在 [0, x] 范围内使用二分查找。对于每个中点 mid，比较 mid * mid 与 x 的大小关系来调整搜索范围。需要注意处理整数溢出问题，可以通过 mid > x / mid 来判断 mid * mid > x。

方法二：牛顿迭代法 使用牛顿迭代公式 x_{n+1} = (x_n + a/x_n) / 2 来逼近平方根，收敛速度较快，但实现相对复杂。

方法三：暴力枚举 从 1 开始逐个测试，直到找到最大的满足 i * i <= x 的整数 i。时间复杂度为 O(√x)，效率较低。

二分查找法在时间复杂度和实现难度之间取得了很好的平衡，是最推荐的解法。关键在于正确处理边界条件和整数溢出问题。

代码实现

class Solution {
public:
    int mySqrt(int x) {
        if (x == 0) return 0;
        
        int left = 1, right = x;
        int result = 0;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            if (mid <= x / mid) {
                result = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return result;
    }
};

class Solution:
    def mySqrt(self, x: int) -> int:
        if x == 0:
            return 0
        
        left, right = 1, x
        result = 0
        
        while left <= right:
            mid = (left + right) // 2
            
            if mid <= x // mid:
                result = mid
                left = mid + 1
            else:
                right = mid - 1
        
        return result

public class Solution {
    public int MySqrt(int x) {
        if (x == 0) return 0;
        
        int left = 1, right = x;
        int result = 0;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            if (mid <= x / mid) {
                result = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return result;
    }
}

/**
 * @param {number} x
 * @return {number}
 */
var mySqrt = function(x) {
    if (x < 2) return x;
    
    let left = 1;
    let right = Math.floor(x / 2);
    
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        let square = mid * mid;
        
        if (square === x) {
            return mid;
        } else if (square < x) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return right;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型二分查找法牛顿迭代法暴力枚举法
时间复杂度O(log x)O(log x)O(√x)
空间复杂度O(1)O(1)O(1)

相关题目