开发者社区> Cool架构> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

Cool说丨力扣69

简介: [69. x 的平方根](https://leetcode-cn.com/problems/sqrtx/)
+关注继续查看

69. x 的平方根

实现 int sqrt(int x) 函数。

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

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

相乘穷举,可能溢出

   int mySqrt(int x) {

    if (x == 0) return 0;

    if (x <= 3) return 1;

    int i = 2;//输入2147395600时报错,(i*i)也是个int,                //int,可保存不了这么大的数字,只好改为                  //long

    for (; i < x / 2; ++i)

    {

        if ( (i * i <= x) && ((i + 1)* (i + 1) > x))

            return i;

    }

   return i;

   }

   int mySqrt(int x) {

    if (x == 0) return 0;

    if (x <= 3) return 1;

    long int i = 2;//改为long后通过

    for (; i < x / 2; ++i)

    {

        if ( (i * i <= x) && ((i + 1)* (i + 1) > x))

            return i;

    }

   return i;

   }

执行用时 :64 ms, 在所有 C++ 提交中击败了5.00%的用户

内存消耗 :8.1 MB, 在所有 C++ 提交中击败了90.43%的用户

二分法会更快一点

   int mySqrt(int x) {

    if (x == 0) return 0;

    if (x <= 3) return 1;

    int min = 0;

    int max = x;

    while (max - min > 1)

    {

        int m = (max + min) / 2;

        if (x / m < m)//用x/m<m,而不是m*m<x可以防止溢出

            max = m;

        else

            min = m;

    }

    return min;

   }

   int mySqrt(int x) {

       long mid = 0;

       long left = 0;

       long right = x;

       while (left < right)

       {

           mid = (left + right + 1) / 2;

           long sq = mid * mid; //或者这样也会更快一点

           if (sq > x)

           {

               right = mid - 1;

           }

           else

           {

               left = mid;

           }

       }

        

       return (int)left;

   }


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
Cool说丨力扣6
6. Z 字形变换
15 0
Cool说丨力扣989
989. 数组形式的整数加法
20 0
Cool说丨力扣414与581
414. 第三大的数 581. 最短无序连续子数组
17 0
Cool说丨力扣11
11. 盛最多水的容器
27 0
Cool说丨力扣718
[718. 最长重复子数组](https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/)
19 0
Cool说丨力扣648
648. 单词替换
22 0
Cool说丨力扣1128
1128. 等价多米诺骨牌对的数量
14 0
Cool说丨力扣3
[3. 无重复字符的最长子串](https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/)
11 0
Cool说丨力扣643
643. 子数组最大平均数 I
12 0
+关注
Cool架构
大三在读,两次国奖,竞赛生。
文章
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载