Leetcode 69 平方根
bobo老师,我用二分搜索做了leetcode 69。虽然通过了,但是还有疑问,以下是代码。按照上课的逻辑,搜索空间是[0, x],目标是寻找mid,使得mid * mid <= x的最大mid。同时注意向上取整的问题。 我之前用int来做,发现总是超时,提示是x很大。所以改成了long型,可以测试通过。
我的问题是,除了用long来扩大整数范围外,这个题目在算法上还有优化空间吗?谢谢!
class Solution { public int mySqrt(int x) { long l = 0; long r = x; while (l < r) { long mid = l + (r - l + 1) / 2; if (mid > x / mid) r = mid - 1; else l = mid; } return (int) l; } }
8
收起
正在回答
1回答
二分搜索的角度,不需要优化了。
但实际上,求平方根,可以使用泰勒级数的方式,更快地求解。不过对于一般的工程师,不需要掌握这个内容。但如果你的数学底子非常好,了解这一点,在面试的时候应该是加分的。
关于这个思路我的参考代码(C++):https://github.com/liuyubobobo/Play-Leetcode/blob/master/0001-0500/0069-Sqrt-x/cpp-0069/main3.cpp
继续加油!:)
恭喜解决一个难题,获得1积分~
来为老师/同学的回答评分吧
0 星