leetcode题目69:x的平方根【python】

简介: leetcode题目69:x的平方根【python】

作者介绍:10年大厂数据\经营分析经验,现任大厂数据部门负责人。

会一些的技术:数据分析、算法、SQL、大数据相关、python

欢迎加入社区:码上找工作

作者专栏每日更新:

LeetCode解锁1000题: 打怪升级之旅

python数据分析可视化:企业实战案例

备注说明:方便大家阅读,统一使用python,带必要注释,公众号 数据分析螺丝钉 一起打怪升级

题目描述

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

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

输入格式
  • x:一个非负整数。
输出格式
  • 返回整数部分的平方根。

示例

示例 1
输入: x = 4
输出: 2
示例 2
输入: x = 8
输出: 2
解释: 8 的平方根是 2.82842..., 因为返回类型是整数,小数部分将被舍去。

方法一:二分查找

解题步骤
  1. 设置边界:设置 left 为 0,rightx
  2. 迭代查找:在 leftright 之间使用二分查找来确定平方根。
  3. 检查中点平方:计算中点的平方,与 x 比较来调整 leftright
完整的规范代码
def mySqrt(x):
    """
    使用二分查找计算平方根
    :param x: int, 输入的非负整数
    :return: int, 平方根的整数部分
    """
    left, right = 0, x
    while left <= right:
        mid = (left + right) // 2
        if mid * mid <= x < (mid + 1) * (mid + 1):
            return mid
        elif mid * mid < x:
            left = mid + 1
        else:
            right = mid - 1
# 示例调用
print(mySqrt(4))  # 输出: 2
print(mySqrt(8))  # 输出: 2
算法分析
  • 时间复杂度:(O(\log n)),其中 n 是输入大小 x,二分查找的时间复杂度。
  • 空间复杂度:(O(1)),只使用了固定的几个变量。

方法二:牛顿迭代法

解题步骤

完整的规范代码
def mySqrt(x):
    """
    使用牛顿迭代法计算平方根
    :param x: int, 输入的非负整数
    :return: int, 平方根的整数部分
    """
    if x < 2:
        return x
    
    x0 = x
    x1 = (x0 + x // x0) // 2
    while x1 < x0:
        x0 = x1
        x1 = (x0 + x // x0) // 2
    return x0
# 示例调用
print(mySqrt(4))  # 输出: 2
print(mySqrt(8))  # 输出: 2
算法分析
  • 时间复杂度:(O(log n)),牛顿迭代法通常具有很快的收敛速度。
  • 空间复杂度:(O(1)),使用了常数个额外空间。

方法三:内置函数法

解题步骤
  1. 直接计算:使用 Python 的内置函数 math.sqrt() 计算平方根。
  2. 结果转换:将得到的浮点数结果转换为整数。
完整的规范代码
import math
def mySqrt(x):
    """
    使用内置函数计算平方根
    :param x: int, 输入的非负整数
    :return: int, 平方根的整数部分
    """
    return int(math.sqrt(x))
# 示例调用
print(mySqrt(4))  # 输出: 2
print(mySqrt(8))  # 输出: 2
算法分析
  • 时间复杂度:(O(1)),内置函数通常优化良好,执行速度快。
  • 空间复杂度:(O(1)),不需要额外空间。

方法四:暴力法

解题步骤
  1. 线性搜索:从 0 开始逐一计算平方,直到平方大于 x
  2. 返回结果:返回最后一个平方不超过 x 的数。
完整的规范代码
def mySqrt(x):
    """
    使用暴力法计算平方根
    :param x: int, 输入的非负整数
    :return: int, 平方根的整数部分
    """
    ans = 0
    while (ans + 1) * (ans + 1) <= x:
        ans += 1
    return ans
# 示例调用
print(mySqrt(4))  # 输出: 2
print(mySqrt(8))  # 输出: 2
算法分析
  • 时间复杂度:(O(sqrt{n})),需要计算直到 x 的平方根。
  • 空间复杂度:(O(1)),使用固定空间。

方法五:位运算法

解题步骤
  1. 位移操作:通过位操作逐步构建结果的每一位,检查平方后是否小于等于 x
  2. 迭代构建结果:从最高位开始尝试,逐步向下调整。
完整的规范代码
def mySqrt(x):
    """
    使用位运算法计算平方根
    :param x: int, 输入的非负整数
    :return: int, 平方根的整数部分
    """
    ans = 0
    bit = 1 << 15  # 从高位开始尝试
    while bit > 0:
        ans |= bit
        if ans * ans > x:
            ans ^= bit  # 如果尝试结果过大,撤销这一位
        bit >>= 1
    return ans
# 示例调用
print(mySqrt(4))  # 输出: 2
print(mySqrt(8))  # 输出: 2
算法分析
  • 时间复杂度:(O(log n)),位运算的复杂度为常数次迭代。
  • 空间复杂度:(O(1)),不需要额外空间。

不同算法的优劣势对比

特征 方法一:二分查找 方法二:牛顿迭代法 方法三:内置函数法 方法四:暴力法 方法五:位运算法
时间复杂度 (O(log n)) (O(log n)) (O(1)) (O(sqrt{n})) (O(log n))
空间复杂度 (O(1)) (O(1)) (O(1)) (O(1)) (O(1))
优势 稳定且高效 收敛速度快,适用于大数 实现简单,运行快速 直观易懂 不使用乘法和除法,节省资源
劣势 需要处理边界条件 初始值依赖较大 受内置函数性能限制 时间成本较高 代码相对复杂,需要位操作知识

应用示例

图形处理软件:在处理图形和游戏开发中,经常需要计算对象的大小或者距离,这时候求平方根是常见的需求。例如,计算点到原点的距离,确定对象是否在视野内等。不同的平方根计算方法可以根据性能需求和精确度要求选择。例如,位运算法因为其高效性,非常适合嵌入式系统或游戏开发中,牛顿迭代法则适用于需要高精度计算的科学计算软件。

欢迎关注微信公众号 数据分析螺丝钉

相关文章
|
22天前
|
C语言
详解Leetcode中关于malloc模拟开辟二维数组问题,涉及二维数组的题目所给函数中的各个参数的解读
详解Leetcode中关于malloc模拟开辟二维数组问题,涉及二维数组的题目所给函数中的各个参数的解读
11 1
|
7天前
|
Python
155. 最小栈 力扣 python 空间换时间 o(1) 腾讯面试题
155. 最小栈 力扣 python 空间换时间 o(1) 腾讯面试题
|
7天前
|
存储 算法 索引
1124. 表现良好的最长时间段 (python) 前缀和 分类讨论 最大长度 力扣 面试题
1124. 表现良好的最长时间段 (python) 前缀和 分类讨论 最大长度 力扣 面试题
|
7天前
|
存储 算法
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
|
1月前
|
存储 算法 调度
力扣中级算法(Python)
力扣中级算法(Python)
|
1月前
|
算法 Python
力扣初级算法(Python)(二)
力扣初级算法(Python)(二)
|
1月前
|
算法 Python
力扣初级算法(Python)(一)
力扣初级算法(Python)(一)
|
1月前
|
算法
【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题:翻转对、买卖股票最佳时机、数组中第K个最大/最小元素
【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题:翻转对、买卖股票最佳时机、数组中第K个最大/最小元素
|
1月前
|
容器
【LeetCode刷题】栈和队列题目练习~
【LeetCode刷题】栈和队列题目练习~
【42页动态规划学习笔记分享】动态规划核心原理详解及27道LeetCode相关经典题目汇总(4)
【42页动态规划学习笔记分享】动态规划核心原理详解及27道LeetCode相关经典题目汇总

热门文章

最新文章

相关实验场景

更多