当前位置: 首页 > article >正文

力扣-数组-69 x的平方根

思路和时间复杂度

  1. 思路:二分寻找符合要求的元素,在mid小于当时的元素时,记录更新结果,这样可以满足要求,而且由于是计算平方,所以可以右边界为之前的一半
  2. 时间复杂度: O(n)      

代码

class Solution {
public:
    int mySqrt(int x) {
        if(x == 0) return 0;
        if(x == 1) return 1;
        // 左闭右闭区间
        long long left = 0, right = x/2;
        long long cur = 0;
        while(left <= right){
            long long mid = (left + right)/2;
            if(mid * mid < x){
                cur = mid;
            }
            if(mid * mid == x){
                cur=mid;
                break;
            }else if(mid*mid > x){
                right = mid-1;
            }else{
                left = mid+1;
            }
        }

        return cur;
    }
};


http://www.kler.cn/a/584335.html

相关文章:

  • 深度学习优化算法全面解析:从理论到实践
  • HCIA-11.以太网链路聚合与交换机堆叠、集群
  • C语言 进阶指针学习笔记
  • Word 小黑第21套
  • 【商城实战(24)】商城性能大揭秘:压力测试与性能监控实战
  • 25年的短剧风口:广告看短剧app开发建设运营及动漫短剧执照 Ai短剧及deepseek和manus等模型Ai接口集成
  • 专题地图的立体表达-基于QGIS和PPT的“千层饼”视图制作实践
  • HTML 样式之 CSS 全面解析
  • CUDA编程之OpenCV与CUDA结合使用
  • Android Retrofit 框架日志与错误处理模块深度剖析(七)
  • Spring Boot基础使用详解
  • 第十七:go 反射
  • docker安装的es报错了?failed to obtain node locks怎么破~
  • linux - ubuntu 使用时一些小问题整理 --- 持续更新
  • 级联树SELECTTREE格式调整
  • AI智能代码疫苗技术,赋能数字化应用内生安全自免疫
  • 通义万相 2.1 × 蓝耘智算:AIGC 界的「黄金搭档」如何重塑创作未来?
  • 解析富集分析中的过表达分析(ORA):原理、应用与优化
  • Axure PR 9 中继器 05 快捷查询
  • 从3b1b到课堂:教育3D化的理想与现实鸿沟