Leetcode 69 平方根

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;
        
    }
}


正在回答

登陆购买课程后可参与讨论,去登陆

1回答

二分搜索的角度,不需要优化了。


但实际上,求平方根,可以使用泰勒级数的方式,更快地求解。不过对于一般的工程师,不需要掌握这个内容。但如果你的数学底子非常好,了解这一点,在面试的时候应该是加分的。


关于这个思路我的参考代码(C++):https://github.com/liuyubobobo/Play-Leetcode/blob/master/0001-0500/0069-Sqrt-x/cpp-0069/main3.cpp


继续加油!:)

问题已解决,确定采纳
还有疑问,暂不采纳

恭喜解决一个难题,获得1积分~

来为老师/同学的回答评分吧

0 星
算法与数据结构
  • 参与学习       2583    人
  • 解答问题       1082    个

慕课网算法名师Liuyubobobo,5年集大成之作 从0到工作5年,算法与数据结构系统解决方案

了解课程
请稍等 ...
意见反馈 帮助中心 APP下载
官方微信

在线咨询

领取优惠

免费试听

领取大纲

扫描二维码,添加
你的专属老师