LeetCode 69. x 的平方根：两种解法详解

LeetCode 上的经典基础题——69. x 的平方根。这道题看似简单却能很好地考察我们对基础算法的理解尤其是循环和二分查找的应用。题目要求很明确给定一个非负整数 x计算它的算术平方根返回整数部分舍去小数并且不能使用任何内置指数函数和算符比如 pow(x, 0.5) 或 x ** 0.5。一、题目核心解读先再明确一下题目边界和要求避免踩坑输入 x 是非负整数0、1、2、3…所以不需要处理负数场景返回值是算术平方根的整数部分比如 x8平方根是2.828…返回2x4返回2x0返回0核心限制不能用内置指数相关方法只能靠基础的循环、判断实现。这道题的核心本质找到最大的整数 res使得 res² ≤ x 且 (res1)² x。所有解法都是围绕这个核心展开的只是效率不同。二、解法一暴力循环简单易理解适合入门1. 思路分析暴力循环的思路非常直观从1开始逐个遍历找到满足 res² ≤ x 的最大整数。但这里有个小优化——我们不需要遍历到 x因为一个数的算术平方根最大不会超过它的一半除了0和1。比如 x100平方根是10刚好是100的一半x101平方根约10.05也不超过50101/2≈50.5。所以遍历范围可以缩小到 1 到 x/2减少循环次数。特殊处理当 x0 时直接返回0因为0的平方根是0当 x1 时x/20.5循环不会执行此时res初始化为1刚好返回正确结果。2. 完整TS代码functionmySqrt_1(x:number):number{if(x0)return0;letres1;for(leti1;ix/2;i){if(i*ix){resi;}}returnres;};3. 优缺点分析优点逻辑简单代码量少容易上手适合刚接触算法的同学理解题目核心缺点效率较低时间复杂度是 O(√x)虽然遍历到x/2但本质还是和平方根成正比。当x很大时比如x2³¹-1即最大的32位非负整数循环次数会非常多可能导致超时。三、解法二二分查找高效最优面试首选既然暴力循环效率不高我们可以用二分查找来优化。二分查找的核心是“缩小查找范围”每次排除一半的无效数据时间复杂度可以降到 O(log x)是这道题的最优解法也是面试中常考的思路。1. 思路分析首先确定查找范围左边界 left0右边界 right 我们可以优化为 Math.max(x 1, 1)。这里的 x 1 是位运算等价于 Math.floor(x/2)比直接除以2更高效而 Math.max(…, 1) 是为了处理 x1 的情况此时x10right设为1避免查找范围出错。然后进行二分循环计算中间值 mid (left right) 1同样用位运算优化等价于 Math.floor((leftright)/2)判断 mid² 与 x 的关系如果 mid² ≤ x说明 mid 可能是我们要找的结果但还可能有更大的数满足条件所以更新 resmid同时将左边界 left 右移leftmid1继续查找右半部分如果 mid² x说明 mid 太大了需要缩小范围将右边界 right 左移rightmid-1循环结束条件left right此时 res 就是满足条件的最大整数即算术平方根的整数部分。2. 完整TS代码functionmySqrt(x:number):number{letleft0;letrightMath.max(x1,1);letres0;while(leftright){constmid(leftright)1;if(mid*midx){leftmid1;resmid;}else{rightmid-1;}}returnres;};3. 关键细节优缺点关键细节为什么用 mid * mid 不会溢出在TS中number类型是64位浮点数对于x≤2³¹-1LeetCode题目中的输入范围mid最大是 (2³¹-1)/2 ≈1e9mid²≈1e18而64位浮点数可以表示的整数范围远大于这个值所以不会溢出。如果是其他语言比如Java可能需要用 long 类型避免溢出这里TS不需要担心。优点效率极高时间复杂度 O(log x)即使x是最大的非负整数循环次数也只有30次左右不会超时缺点逻辑比暴力循环稍复杂需要理解二分查找的“缩小范围”思路新手可能需要多调试几次。四、两种解法对比实战建议解法时间复杂度空间复杂度适用场景暴力循环O(√x)O(1)入门理解题目、x较小的场景二分查找O(log x)O(1)面试、x较大的场景推荐五、总结与解题感悟综上所述LeetCode 69. x 的平方根作为一道基础且经典的算法题型在算法学习与面试考核中均占据重要地位。从算法学习维度来看该题目无需依赖复杂数据结构与高级算法思想是检验开发者对循环逻辑、二分查找两大基础算法掌握程度的核心载体既能帮助新手快速建立算法解题思维也能让有一定基础的开发者巩固核心知识点、梳理算法优化逻辑。从面试场景来看该题目是大厂面试中考察基础算法思维的高频题型面试官不仅关注解题代码的正确性更注重开发者对不同解法的选择逻辑、时间复杂度与空间复杂度的分析能力以及对边界场景的处理细节而本题的两种核心解法暴力循环与二分查找恰好能全面展现开发者的基础算法素养与问题优化能力。此外该题目还具备极强的延伸性其核心解题思想可迁移至平方根相关的拓展题型进一步体现了其作为基础题目的实用价值与学习意义。