Leetcode刷题-69. x 的平方根

水深无声 2022-10-24 05:51 128阅读 0赞

# 题目 #

实现 int sqrt(int x) 函数。计算并返回 x 的平方根，其中 x 是非负整数。由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

**备注**  
来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/sqrtx  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

# 解法1 #

一步步往前，效率并不高

class Solution {
        public int mySqrt(int x) {
            if (x < 2) {
                return x;
            }
            int pre = 2;
            int result = x / pre;
            while (result > (pre + 1)) {
                result = x / ++pre;
            }
            return Math.min(pre, result);
        }
    }

### 解法2 ###

主要是看别人的答案，用的是二分法，时间效率比较快。

### 解法3 ###

与解法2区别，用除法，避免使用long（x过大时），收敛更快（能快多少，不太清楚了）

class Solution {
        public int mySqrt(int x) {
            int left = 0;
            int right = (x >>> 1) + 1;
            while (left < right) {
                int mid = (left + right + 1) >>> 1;
                int midOther = x / mid;
                if (Math.abs(midOther - mid) < 2) {
                    return Math.min(mid, midOther);
                }
                if (midOther > mid) {
                    left = mid;
                    if (right > midOther - 1) {
                        right = midOther - 1;
                    }
                } else {
                    right = mid - 1;
                    if (left < midOther) {
                        left = midOther;
                    }
    
                }
            }
            return left;
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，128人围观）

还没有评论，来说两句吧...

相关阅读

相关 leetcode69 x的平方根

实现 int sqrt(int x) 函数。计算并返回 x 的平方根，其中 x 是非负整数。由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。示例 1:

朱雀/ 2023年06月20日 06:23/ 0 赞/ 189 阅读

相关【LeetCode 69】x的平方根

题目描述实现 int sqrt(int x) 函数。计算并返回 x 的平方根，其中 x 是非负整数。由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

怼烎@/ 2022年12月08日 05:08/ 0 赞/ 144 阅读

相关 LeetCode 69. x 的平方根

69. x 的平方根 [https://leetcode-cn.com/problems/sqrtx/solution/x-de-ping-fang-gen-by-lee

亦凉/ 2022年11月07日 05:53/ 0 赞/ 174 阅读

相关 Leetcode刷题-69. x 的平方根

题目实现 int sqrt(int x) 函数。计算并返回 x 的平方根，其中 x 是非负整数。由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。备注

水深无声/ 2022年10月24日 05:51/ 0 赞/ 129 阅读

相关 leetcode69x的平方根

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

约定不等于承诺〃/ 2022年10月08日 13:22/ 0 赞/ 247 阅读

相关 Leetcode 69. x 的平方根

题目重述实现 int sqrt(int x) 函数。计算并返回 x 的平方根，其中 x 是非负整数。由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

﹏ヽ暗。殇╰゛Y/ 2022年09月09日 06:28/ 0 赞/ 233 阅读

相关 Leetcode 69. x 的平方根

题目重述实现 int sqrt(int x) 函数。计算并返回 x 的平方根，其中 x 是非负整数。由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

古城微笑少年丶/ 2022年09月05日 15:44/ 0 赞/ 220 阅读

相关【LeetCode】69. x 的平方根

题目链接：[https://leetcode-cn.com/problems/sqrtx/description/][https_leetcode-cn.com_problem

水深无声/ 2022年05月09日 14:50/ 0 赞/ 260 阅读

相关 LeetCode 69. x 的平方根

1. x 的平方根题目实现 int sqrt(int x) 函数。计算并返回 x 的平方根，其中 x 是非负整数。

深碍√TFBOYSˉ_/ 2022年03月26日 14:48/ 0 赞/ 294 阅读

相关 leetcode 69. x 的平方根

69. x 的平方根 > 难度：简单 > > 题库地址：[leetcode-cn.com/problems/sq…][leetcode-cn.com_problems_

灰太狼/ 2022年01月20日 11:59/ 0 赞/ 290 阅读