69.x的平方根

LeetCode LeetCode 数学二分查找

发布时间 : 2000-01-10 00:06

字数:1.7k 阅读 :

评论:

69.x的平方根

69.x的平方根

69.1 题目

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

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

注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5。

示例 1：

输入：x = 4
输出：2

示例 2：

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

提示：

0 <= x <= 2^31 - 1

69.2 题解

方法一：二分查找法

思路

在 [1, x] 范围内二分查找，找到最大的 mid 使得 mid² ≤ x。使用 long 类型避免 mid * mid 溢出。当 mid² == x 时直接返回；当 mid² < x 时记录结果并继续向右找；当 mid² > x 时向左找。最终返回记录的结果（整数部分）。

核心思想：二分查找最大的满足 mid² ≤ x 的整数。

具体步骤：

如果 x <= 1：直接返回 x。
在 [1, x] 范围内二分：
- 如果 mid² == x：返回 mid
- 如果 mid² < x：记录 mid，继续向右找
- 如果 mid² > x：向左找
返回记录的结果。

举例：对于 x = 8：

left=1, right=8：mid=4，16 > 8，right=3
left=1, right=3：mid=2，4 < 8，result=2，left=3
left=3, right=3：mid=3，9 > 8，right=2
left > right，返回 result=2

复杂度分析

时间复杂度：O(log x)，二分查找。
空间复杂度：O(1)，只使用常数额外空间。

代码

// 方法一：二分查找法
// 在1-x不断二分查找找到最接近的整数
static int MySqrt1(int x)
{
    // 如果 x 等于 0 或 1，直接返回 x，因为其平方根为自身
    if (x == 0 || x == 1)
    {
        return x;
    }

    // 初始化左边界为 1，右边界为 x，以及结果变量为 0
    long left = 1;
    long right = x;
    long result = 0;

    // 使用二分查找法寻找 x 的平方根
    while (left <= right)
    {
        // 计算中间值 mid
        long mid = left + (right - left) / 2;

        // 如果 mid 的平方等于 x，直接返回 mid
        if (mid * mid == x)
        {
            return (int)mid;
        }
        // 如果 mid 的平方小于 x，说明平方根在右半部分，更新左边界和记录结果的变量
        else if (mid * mid < x)
        {
            left = mid + 1;
            result = mid; // 记录当前 mid，因为要返回整数部分
        }
        // 如果 mid 的平方大于 x，说明平方根在左半部分，更新右边界
        else
        {
            right = mid - 1;
        }
    }

    // 返回整数部分结果
    return (int)result;
}

方法二：牛顿迭代法

思路

牛顿迭代法用于逼近方程的根。对于求 √x，迭代公式为 r = (r + x / r) / 2。

初始值设为 x，每次迭代让 r 逼近真实的平方根。

当 r² ≤ x 时停止迭代，返回 r 的整数部分。

收敛速度非常快，通常几次迭代即可得到结果。

举个例子：x = 8（与文中代码一致，/ 为整数除法）

r = 8，r * r > 8：r = (8 + 8/8) / 2 = (8 + 1) / 2 = 4
r = 4，16 > 8：r = (4 + 8/4) / 2 = (4 + 2) / 2 = 3
r = 3，9 > 8：r = (3 + 8/3) / 2 = (3 + 2) / 2 = 2
r = 2，4 <= 8，停止，返回 2

复杂度分析

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

代码

// 方法二：牛顿迭代法
// 思路：牛顿迭代法用于逼近方程的根，对于求解平方根问题，迭代公式为 r = (r + x / r) / 2。
// 1. 选择初始值 r 为 x。
// 2. 使用迭代公式逐步逼近 x 的平方根，直到 r * r 不再大于 x。
// 3. 返回整数部分结果，即 r 的整数部分。
static int MySqrt2(int x)
{
    // 如果 x 等于 0 或 1，直接返回 x，因为其平方根为自身
    if (x == 0 || x == 1)
    {
        return x;
    }

    // 初始化变量 r 为 x
    long r = x;

    // 使用牛顿迭代法逼近 x 的平方根
    while (r * r > x)
    {
        r = (r + x / r) / 2;
    }

    // 返回整数部分结果
    return (int)r;
}

69.3 代码

using System;

class Program
{
    static void Main()
    {
        #region 题目

        // 给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
        // 由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
        // 注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

        // 示例 1：
        // 输入：x = 4
        // 输出：2

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

        // 提示：
        // 0 <= x <= 231 - 1

        #endregion

        #region 测试

        // 示例 1
        int x1 = 4;
        int result1 = MySqrt1(x1);
        Console.WriteLine($"示例1 方法1 输出：{result1}");
        int result1_2 = MySqrt2(x1);
        Console.WriteLine($"示例1 方法2 输出：{result1_2}");

        // 示例 2
        int x2 = 8;
        int result2 = MySqrt1(x2);
        Console.WriteLine($"示例2 方法1 输出：{result2}");
        int result2_2 = MySqrt2(x2);
        Console.WriteLine($"示例2 方法2 输出：{result2_2}");

        #endregion
    }

    #region 答案

    // 方法一：二分查找法
    // 在1-x不断二分查找找到最接近的整数
    static int MySqrt1(int x)
    {
        // 如果 x 等于 0 或 1，直接返回 x，因为其平方根为自身
        if (x == 0 || x == 1)
        {
            return x;
        }

        // 初始化左边界为 1，右边界为 x，以及结果变量为 0
        long left = 1;
        long right = x;
        long result = 0;

        // 使用二分查找法寻找 x 的平方根
        while (left <= right)
        {
            // 计算中间值 mid
            long mid = left + (right - left) / 2;

            // 如果 mid 的平方等于 x，直接返回 mid
            if (mid * mid == x)
            {
                return (int)mid;
            }
            // 如果 mid 的平方小于 x，说明平方根在右半部分，更新左边界和记录结果的变量
            else if (mid * mid < x)
            {
                left = mid + 1;
                result = mid; // 记录当前 mid，因为要返回整数部分
            }
            // 如果 mid 的平方大于 x，说明平方根在左半部分，更新右边界
            else
            {
                right = mid - 1;
            }
        }

        // 返回整数部分结果
        return (int)result;
    }

    // 方法二：牛顿迭代法
    // 思路：牛顿迭代法用于逼近方程的根，对于求解平方根问题，迭代公式为 r = (r + x / r) / 2。
    // 1. 选择初始值 r 为 x。
    // 2. 使用迭代公式逐步逼近 x 的平方根，直到 r * r 不再大于 x。
    // 3. 返回整数部分结果，即 r 的整数部分。
    static int MySqrt2(int x)
    {
        // 如果 x 等于 0 或 1，直接返回 x，因为其平方根为自身
        if (x == 0 || x == 1)
        {
            return x;
        }

        // 初始化变量 r 为 x
        long r = x;

        // 使用牛顿迭代法逼近 x 的平方根
        while (r * r > x)
        {
            r = (r + x / r) / 2;
        }

        // 返回整数部分结果
        return (int)r;
    }
    

    #endregion
}

69.4 运行结果

示例1 方法1 输出：2
示例1 方法2 输出：2
示例2 方法1 输出：2
示例2 方法2 输出：2

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com