leetcode
leetcode 3001 ~ 3050
x 的平方根

x 的平方根

难度:

标签:

题目描述

English description is not available for the problem. Please switch to Chinese.

代码结果

运行时间: 26 ms, 内存: 16.1 MB

/*
 * 思路：
 * 使用Java Stream的特性可以简化代码，通过生成一个范围流并过滤出小于等于x平方根的最大整数。
 * 不过这种方法效率较低，实际开发中不推荐。
 */
import java.util.stream.IntStream;

public class Solution {
    public int sqrt(int x) {
        return IntStream.rangeClosed(0, x)
                        .filter(i -> i * i <= x)
                        .max()
                        .orElse(0);
    }
}

解释

方法:

本题解使用二分查找算法来寻找非负整数 x 的平方根。初始化左边界 l 为 0，右边界 r 为 x。在循环中，计算中间值 mid 为 l 和 r 的平均值。若 mid 的平方大于等于 x，则将右边界 r 更新为 mid，否则将左边界 l 更新为 mid + 1。循环直到左边界小于右边界。最后，如果 l 的平方等于 x，则返回 l，否则返回 l-1，因为此时 l 的平方大于 x 且 (l-1) 的平方小于 x。

时间复杂度:

O(log x)

空间复杂度:

O(1)

代码细节讲解

🦆
为什么在计算中点时选择使用`(l + r) // 2`而不是`(l + r + 1) // 2`？
▷
在二分查找中，`(l + r) // 2`确保了中点mid向下取整，这有助于防止在l和r非常接近时，mid计算结果永远不会超过r，避免了可能的无限循环。另外，这种方式能保证mid永远不会等于r，从而在更新右界时可以直接设置为mid，简化逻辑。使用`(l + r + 1) // 2`可能会导致计算的mid偏大，从而在某些情况下造成错误或效率降低。
🦆
在二分查找时，为什么当`mid * mid >= x`时更新右边界`r`为`mid`，而不是`mid - 1`？
▷
在二分查找中，当`mid * mid >= x`时更新右边界为`mid`而不是`mid - 1`是为了保证不错过平方根的正确值。如果`mid * mid == x`，则mid就是我们要找的平方根，如果我们设置`r = mid - 1`，就会错过这个正确值。只有当我们确定`mid * mid > x`时，才知道平方根肯定小于mid，但这个逻辑在判断中已包含，使得代码更加简洁和直观。
🦆
如果输入的`x`非常大，比如接近整型的最大值，这个算法处理大数时的性能如何？是否会有整数溢出的问题？
▷
本算法在处理非常大的`x`值时性能良好，因为它的时间复杂度为O(log x)，即随着输入值的增大，所需的步骤增长是对数的。对于整数溢出的问题，由于在计算`mid * mid`时可能超出整数范围，Python自动处理大整数，不会发生溢出错误。在其他语言如Java或C++中，可能需要特别处理以避免溢出，例如通过使用长整型或在比较之前检查可能的溢出。

相关问题

按权重随机选择爱吃香蕉的狒狒