【Day 37 】2021-10-16 - 69. x 的平方根

[azl397985856]

69. x 的平方根

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/sqrtx

前置知识

• 二分法

  题目描述

  
  实现 int sqrt(int x) 函数。

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

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

示例 1:

输入: 4 输出: 2 示例 2:

输入: 8 输出: 2 说明: 8 的平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去

[yanglr]

思路

sqrt(x)是C语言中 math.h 中的库函数, 好像是用牛顿切线法实现的。 而我们自己来做，既可以用牛顿切线法，也可以用二分搜索实现。

方法1: 牛顿切线法

在浮点数区间 [preX, nextX] (变量名末尾的X表示横坐标)上不断地迭代, 区间初始化为 [0, 1], 在区间[0, 1]上开始找，不断调整区间的左右边界, 左右边界的误差小于 1e-7 就结束循环. preX是区间的边界bound之一, 特定情况下preX和nextX可能会左右互换.

最后 nextX需要从double转为int, 然后返回.

迭代公式为: nextX = (nextX + x/nextX) / 2.0;

代码

实现语言: C++

class Solution {
public:
    int mySqrt(int x) {
        const int eps = 1e-7;
        if (x == 0) return 0;
        double preX = 0; /* preX是区间的边界bound之一, 特定情况下preX和nextX(变量名末尾的X表示横坐标)可能会左右互换. 在区间[0, 1]上开始找，不断调整区间的边界 */
        double nextX = 1;
        while (nextX - preX > eps || preX - nextX > eps)
        {
            preX = nextX;
            nextX = (nextX + x / nextX) / 2.0;
        }
        return (int)nextX; // int
    }
};

复杂度分析

• 时间复杂度：O(logN)
• 空间复杂度：O(1)

方法2: 二分搜索

二分的流程:

1.确定二分的边界

2.编写二分的代码框架

3.设计一个check(性质)

4.判断一下区间如何更新

代码

实现语言: C++

class Solution {
public:
    int mySqrt(int x) {
        // 二分搜索
        int l = 0, r = x;
        while (l < r)
        {
            auto mid = (l + (long long)r + 1)/2;
            // check(性质): t^2 <= x
            if (mid <= x/mid) /* 防止溢出 */
                l = mid;
            else r = mid - 1;
        }
        return l;  // 或 r, 循环结束时 l = r
    }
};

复杂度分析

• 时间复杂度：O(logN)
• 空间复杂度：O(1)

[pophy]

思路

• 2分猜答案

Java Code

class Solution {
    public int mySqrt(int x) {
        long low = 0, high = x;
        while (low + 1 < high) {
            long mid = low + (high - low) / 2;
            if (mid * mid == x) {
                return (int)mid;
            } else if (mid * mid > x) {
                high = mid;
            } else {
                low = mid;
            }
        }
        if (high * high <= x) {
            return (int)high;
        }
        return (int)low;
    }
}

时间&空间

• 时间 O(log(n))
• 空间 O(1)

[yachtcoder]

Binary search. O(lgn), O(1)

class Solution:
    def mySqrt(self, x: int) -> int:
        l, r = 0, x
        while l <= r:
            mid = (l+r)//2
            if mid * mid <= x:
                l = mid + 1
            else:
                r = mid - 1
        return r

[mmboxmm]

思路

Binary Search

代码

class Solution {
    public int mySqrt(int x) {
        long low = 0, high = x;
        while (low + 1 < high) {
            long mid = low + (high - low) / 2;
            if (mid * mid == x) {
                return (int)mid;
            } else if (mid * mid > x) {
                high = mid;
            } else {
                low = mid;
            }
        }
        if (high * high <= x) {
            return (int)high;
        }
        return (int)low;
    }
}

复杂度

O(logn)

[BpointA]

思路

二分法

Python3代码

class Solution:
    def mySqrt(self, x: int) -> int:
        left=0
        right=x
        while left<=right:
            mid=(left+right)//2
            if mid**2<=x and (mid+1)**2>x:
                return mid
            elif mid**2>x:
                right=mid-1
            else:
                left=mid+1
        return 0

复杂度

时间复杂度：O(logn)

空间复杂度：O(1)

[yuxiangdev]

while (l < r) 做不了这道题。 必须得用左闭右闭区间 public int mySqrt(int x) { if (x == 0) return 0; int l = 1; int r = x; while (l <= r) { int m = l + (r - l) / 2; if (m > x / m) { r = m - 1; } else { l = m + 1; } } return l - 1; } }

[fzzfgbw]

思路

二分

代码

func mySqrt(x int) int {
    l:=1
    r:=x
    for l<=r {
        m:=(r-l)/2+l
        temp:= m*m
        if temp == x{
            return m
        }else if temp>x{
            r = m-1
        }else{
            l = m+1
        }
    }
    return r
}

复杂度分析

• 时间复杂度：O(logn)
• 空间复杂度：O(1)

[zliu1413]

class Solution: def mySqrt(self, x: int) -> int: a=0 b=x while a<=b: mid = a + (b-a)//2 if mid2-x<0: a = mid+1 elif mid2-x>0: b = mid-1 else: return mid return b

time: O(logn) space: O(1)

[Menglin-l]

思路：

观察可知，平方根均小于该数/2，所以不需要从头找到尾，用二分即可。

---

代码部分：

class Solution {
    public int mySqrt(int x) {
        int right = x;
        int left = 0;

        while (left < right) {
            int mid = left + (right - left) / 2; // 向下取整
            if ((long) mid * mid >= x) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return (long) left * left == x ? left : left - 1; 
    }
}

---

复杂度：

Time: O(logN)，N为x

Space: O(1)

[xinhaoyi]

69. Sqrt(x)

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

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

注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

示例 1：

输入：x = 4 输出：2 示例 2：

输入：x = 8 输出：2 解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。

思路一

用牛顿迭代法求根即可

代码

class Solution {
    public int mySqrt(int x) {
        //原式转化为求f(x) = x^2 - a = 0 的解, a是我们的x
        //采用牛顿迭代法
        //Xn = Xn-1 - f(Xn-1) / f'(Xn - 1);
        //转化为：Xn = Xn-1 - f(Xn-1) / (2 * Xn-1);
        //进一步转化为：Xn = ( Xn-1 ^2 + a ) / (2 * Xn-1) = (Xn-1 + a / Xn-1) / 2;
        if(x == 0){
            return x;
        }

        double a = x;
        double err = 1e-15;
        //初始值设置为 x / 2
        double num = a;
        //结束条件可以视作 ：1 - x / num ^ 2  =  0
        //可以转化为：|1 - x / num ^ 2| < err(无穷小)
        //进一步转化为：|num - x / num| < err * num
        while(Math.abs(num - a / num) > err * num) {
            num = (num + a / num) / 2.0;
        }

        return (int)num;
    }
}

复杂度分析：

时间复杂度：$O(logn)$

空间复杂度：$O(1)$

[florenzliu]

---

Explanation

• use binarySearch

Python

class Solution:
    def mySqrt(self, x: int) -> int:
        if x < 2:
            return x
        left, right = 2, x // 2
        while left <= right:
            pivot = left + (right-left)//2
            num = pivot * pivot
            if num > x:
                right = pivot - 1
            elif num < x:
                left = pivot + 1
            else:
                return pivot
        return right

Complexity:

• Time Complexity: O(logN)
• Space Complexity: O(1)

[heyqz]

class Solution:
    def mySqrt(self, x: int) -> int:

        left, right = 1, x

        while left <= right:
            mid = left + (right - left) // 2
            if mid * mid > x:
                right = mid - 1
            else:
                left = mid + 1

        return right

time complexity: O(logn) space complexity: O(1)

[comst007]

69. 求平方根

---

思路

二分

代码

• C++

class Solution {
public:
    int mySqrt(int x) {

        long long  ll, rr;
        ll = 0;
        rr = x;
        int mid;
        while(ll < rr){
            mid = ll + rr + 1 >> 1;
            if(mid  <= x / mid){
                ll = mid;
            }else{
                rr = mid - 1;
            }
        }
        return ll ;
    }
};

---

复杂度分析

n一个正整数

• 时间复杂度 O(logn)。
• 空间复杂度 O(1)。

[pan-qin]

idea

two pointer. Note when check if square is equal to target, make sure explicitly convert mid to long, otherwise some edge case will fail.

Complexity:

Time: O(log n) Space: O(1)

Code:

class Solution {
    public int mySqrt(int x) {
        int left=0, right=x;
        while(left<=right) {
            int mid = left+ (right-left)/2;
            long square = (long) mid*mid;
            if(square==x) 
                return mid;
            else if(square>x)
                right=mid-1;
            else 
                left=mid+1;
        }
        return right;
    }
}

[BlueRui]

Problem 69. Sqrt(x)

Algorithm

• Use binary search.
• The trick here is we can use left <= right as the while loop condition, and progress with left = mid + 1 and right = mid - 1. The final result will be right. The reason is we are finding the largest integer that is less than or equal to the actual square root.
• Another trick is to use long for square value to avoid overflow.

Complexity

• Time Complexity: O(logN) where N is the input value.
• Space Complexity: O(1).

Code

Language: Java

public int mySqrt(int x) {
    int left = 0;
    int right = x;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        long square = (long) mid * mid;
        if (square == x) {
            return mid;
        } else if (square < x) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return right;
}

[zhangzhengNeu]

class Solution { public int mySqrt(int x) { int right = x; int left = 0;

    while (left < right) {
        int mid = left + (right - left) / 2; // 向下取整
        if ((long) mid * mid >= x) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }

    return (long) left * left == x ? left : left - 1; 
}

}

[wangzehan123]

class Solution {
int mySqrt(int x) 
    {
        if(x == 1)
            return 1;
        int min = 0;
        int max = x;
        while(max-min>1)
        {
            int m = (max+min)/2;
            if(x/m<m)
                max = m;
            else
                min = m;
        }
        return min;
    }
}

复杂度分析

令 n 为数组长度。

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

[xj-yan]

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

Time Complexity: O(logN), Space Complexity: O(1)

[q815101630]

思路：

先看完了一大半的二分讲义，再来做这道题就轻车熟路了。这讲义，仔细看真的是满满干货！

先上模板，如果power > x 那么压缩右边界，如果 小于，那么压缩左边界。最后为什么return r， 关于这一点我是先试了几个例子，知道 r 是最后正确答案。但是原理上来说，我的理解是因为 我们 是对答案做floor()，如果最后答案平方小于 x，我们最后会让 l = mid+1, 这是不安全的，因为我们不确定最后 l 的平方也小于 x，而如果最后取 r， 那一定是安全的。

class Solution:
    def mySqrt(self, x: int) -> int:
        if x == 1:
            return 1

        l = 0
        r = x//2
        while l<=r:
            mid = l + (r-l)//2
            power = mid*mid
            if power == x:
                return mid
            elif power > x:
                r = mid - 1
            else:
                l = mid + 1
        return r

时间： 二分 log(N) 空间： O(1)

[skinnyh]

Note

• Binary Search in [0, x]

Solution

class Solution:
    def mySqrt(self, x: int) -> int:
        start, end = 0, x
        while start + 1 < end:
            mid = (start + end) // 2
            if mid * mid == x:
                return mid
            if mid * mid < x:
                start = mid
            else:
                end = mid
        return end if end * end <= x else start

Time complexity: O(logN)

Space complexity: O(1)

[RocJeMaintiendrai]

题目

https://leetcode-cn.com/problems/sqrtx/

思路

二分法。最后如果mid < x / mid 说明mid是舍掉小数的。否则返回mid - 1。

代码

class Solution {
    public int mySqrt(int x) {
        if(x == 0) return 0;
        if(x == 1) return 1;
       int left = 1;
       int right = x;
       int mid = 0;
       while(left <= right) {
           mid = left + (right - left) / 2;
           if(mid == x / mid) {
               return mid;
           } else if(mid < x / mid) {
               left = mid + 1;
           } else {
               right = mid - 1;
           }
       }
       if(mid < x / mid) {
           return mid;
       } else {
           return mid - 1;
       }
    }
}

复杂度分析

时间复杂度

O(logN)

空间复杂度

O(1)

[Laurence-try]

思路

二分法

代码

使用语言：Python3

class Solution:
    def mySqrt(self, x: int) -> int:
        start = 0
        des = x
        mid = (start + des) // 2
        while start <= des:
            if mid * mid > x:
                des = mid - 1
                mid = (start + des) // 2
            else:
                start = mid + 1
                mid = (start + des) // 2
        return mid

复杂度分析 时间复杂度：O(logN) 空间复杂度：O(1)

[a244629128]

var mySqrt = function(x) {
  if (x < 1) return 0;
  let high = x;
  let low = 1;
  let mid = 0;
  while(low + 1 < high) {
    mid = Math.floor((high + low)/2);
    if (mid * mid > x) {
      high = mid;
    } else if (mid * mid < x) {
      low = mid;
    } else {
      return mid;
    }
  }
  return low;
};

[qyw-wqy]

class Solution {
    public int mySqrt(int x) {
        if (x < 2) return x;
        int l = 0;
        int r = x / 2;
        while (l < r) {
            int mid = l + (r - l + 1) / 2;
            if (mid > x / mid) r = mid - 1;
            else l = mid;
        }
        return l;
    }
}

Time: O(longN)\ Space: O(1)

[hwpanda]

Language: JavaScript

var mySqrt = function (x) {
    if (x === 0) return 0;
    if (x === 1) return 1;
    var left = 0;
    var right = x;
    var mid;
    var sqrt;
    var ans;
    while (left < right) {
        mid = Math.floor((left + right) / 2);
        sqrt = mid * mid;
        if (sqrt < x) {
            ans = mid;
            left = mid + 1;
        } else if (sqrt > x) {
            right = mid;
        } else {
            return mid;
        }
    }
    return ans;
};

[zhangzz2015]

思路

• 方法1， 使用binary search。先定义上下界 [ 1 x/2+1] 每次判断 middle middle == target。排除半边空间，再剩下空间继续查找，注意可能有整数超出，使用除法判断 middle == target/middle。最后退出得到 [ right right < x < left* left 因为是往下clamp，返回right。时间复杂度为O(logN) ，空间复杂度为O(1)。
• 方法2， 采用求根的方法，使用NR迭代方法 f(y) =yy - x =0 迭代关系为 df/dy deltaY = - f(y_0) df/dy = 2y deltaY = (y0y0 -x)/(-2y0) // newY = y0 + deltaY; 具体的时间的复杂度应该会快于方法1，因为是二次收敛， 空间复杂度为O(1)。

关键点

代码

• 语言支持：C++

C++ Code:

class Solution {
public:
    int mySqrt(int x) {

        if(x==0)
            return 0; 

        int left =1; 
        int right = x/2+1; 

        while(left <=right)
        {
            int middle = left + (right - left)/2; 
            if(  middle == x/middle )
                return middle; 
            else if( middle< x/middle  )
            {
                left = middle+1; 
            }
            else
            {
                right = middle-1; 
            }
        }
        //   [right left]
        return  right; 
    }
};

class Solution {
public:
    int mySqrt(int x) {

        ///  sqrt(x) = y  --- > y*y -x = 0 ---> 
        /// use NR method.   y0*y0 - x  = f(y0)
        //   deltaY =   (y0*y0 -x)/(-2y0)
        // newY = y0 + deltaY; 
        if(x==0)
            return 0; 
        int y0 = x/2+1; // avoid y0 =0 
        int deltaY=0;
        while(1)
        {
           // cout<<"y0"<<y0<<"\n";
            deltaY= -(y0 - x/y0)/2;

            //cout<<"deltaY"<<deltaY<<"\n";
            if(deltaY ==0)
                break;                 
            else
                y0 +=deltaY;
            //cout<<"y0:"<<y0<<"\n";
        }
        if(y0 -x/y0 >0)
                y0 -=1;        
        return y0;        
    }
};

[falconruo]

思路:

二分查找:

1. 利用两个指针l, r分别指向0，x
2. 执行循环：
   • 每次取中间值mid, 使其为l与r的和的一半,为了防止溢出注意将mid的类型定义为long
   • 判断mid的平方与值x的关系： 1) 如果mid的平方小于等于x，而mid + 1的平方大于x, 则表示mid为x的平方根，直接返回mid 2) 如果仅mid的平方小于等于x，则说明目标值在右半部分，将左指针l向右移动到mid + 1 3) 如果仅mid的平方大于x，则说明目标值在左半部分，将右指针l向左移动到mid - 1
3. 返回左指针l

复杂度分析:

时间复杂度: O(logx)

空间复杂度: O(1)

代码(C++):

class Solution {
public:
    int mySqrt(int x) {
        int l = 0, r = x;

        while (l <= r) {
            long mid = l + (r - l)/2;

            if ((mid * mid <= x) && ((mid + 1)*(mid + 1) > x))
                return int(mid);
            else if (mid * mid > x)
                r = mid - 1;
            else
                l = mid + 1;
        }

        return l;
    }
};

[leo173701]

class Solution:
    def mySqrt(self, x: int) -> int:
        if x==0 or x==1:
            return x
        left = 0
        right =int(x/2)
        while left<=right:
            mid = (left + right) >> 1
            if mid*mid <=x and (mid+1)*(mid+1)>x:
                return mid
            elif mid*mid < x:
                left = mid +1
            else:
                right =mid -1

[Tao-Mao]

Idea

Binary Search

Code

class Solution {
    public int mySqrt(int x) {
        if (x < 2) return x;
        int start = 1;
        int end = x;
        int mid = 0;
        while (start <= end) {
            mid = start + (end-start)/2;
            if (mid * mid == x) return mid;
            else if (mid > x/mid) end = mid - 1;
            else start = mid + 1;
        }
        return end;
    }
}

Complexity

• Time: O(logn)
• Space: O(1)

[RonghuanYou]

class Solution:
    def mySqrt(self, x: int) -> int:
        if x == 1:
            return x
        left, right = 1, x // 2
        while left <= right:
            mid = (left + right) // 2
            if mid > x / mid:
                right = mid - 1
            else:
                left = mid + 1
        return left - 1

[chen445]

代码

class Solution:
    def mySqrt(self, x: int) -> int:
        if x <2:
            return x
        left,right=2,x//2
        while left<=right:
            mid=left+(right-left)//2
            if mid*mid>x:
                right=mid-1
            elif mid*mid <x:
                left=mid+1
            else:
                return mid
        return right

复杂度

Time: O(logn)

Space: O(1)

[Daniel-Zheng]

思路

二分法。

代码(C++)

class Solution {
public:
    int mySqrt(int x) {
        int l = 1, r = x, mid;
        while (l <= r){
            mid = l + (r - l) / 2;
            if(x / mid > mid) l = mid + 1;
            else if (x / mid < mid) r = mid - 1;
            else return mid;
        }
        return r;
    }
};

复杂度分析

• 时间复杂度：O(LogN)
• 空间复杂度：O(1)

[ningli12]

思路

二分法。

代码

class Solution {
    public int mySqrt(int x) {
        if(x == 0) return 0;
        if(x == 1) return 1;
        int low = 2;
        int high = x/2;
        while(low <= high){
            int mid = low + (high - low)/2;
            long num = mid * mid;
            if(num > x) high = mid -1;
            else if(num < x)low = mid + 1;
            else return mid;
        }
        return high;
    }
}

复杂度分析

• 时间复杂度：O(LogN)
• 空间复杂度：O(1)

[sxr000511]

class Solution: def mySqrt(self, x: int) -> int: ans, l, r = 0, 0, x while l <= r: mid = (l + r) // 2 if mid 2 > x: r = mid - 1 if mid 2 <= x: ans = mid l = mid + 1 return int(ans)

[akxuan]

binary search 的模板 时间复杂度 （logN) 空间复杂度： 1

class Solution:
    def mySqrt(self, x: int) -> int:

        if x == 1:
            return 1

        start, end = 1, x

        while start+1 < end :
            mid = start + int((end - start)/2)

            if mid*mid == x: return mid
            elif mid*mid < x: start = mid
            else: end = mid
        if start*start == x: return start
        if end*end == x : return end
        return start

[ychen8777]

思路

二分查找

代码

class Solution {
    public int mySqrt(int x) {
        int l = 0, r = x, res = -1;

        while (l <= r) {

            int mid = l + (r - l) / 2;
            if ((long) mid * mid <= x) {
                res = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }

        }

        return res;
    }
}

复杂度

时间、空间: O(1)

[nonevsnull]

思路

• 拿到题的直觉解法
  • 二分的题，目标是将题目匹配到模板；
  • 没匹配，就没想清楚，做出来也没意义；下次还是错；
  • Sqrt不一定能找到刚好等于的数，对于n=4来说，是个精确匹配，但对于n=8来说，问题的性质都变了；
  • 根据题目条件，省略小数，综合考虑，匹配模板： 寻找最右符合条件的值；也就是最接近，但不超过sqrt(n)的值

AC

代码

class Solution {
    public int mySqrt(int x) {
        int left = 0, right = x;

        while(left <= right){
            int mid = left + (right - left) / 2;
            if((long)mid * mid <= x){
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        if(right < 0 || (long)right * right > x){
            return -1;
        }

        return right;
    }
}

复杂度

time: O(logN) space: O(1)

[kidexp]

thoughts

二分法

code

class Solution:
    def mySqrt(self, x: int) -> int:
        """
        classic binary search
        """
        start, end = 0, x
        while start <= end:
            mid = (start + end) // 2
            mid_square = mid * mid
            if mid_square <= x < (mid+1) * (mid+1):
                return mid
            elif mid_square < x :
                start = mid + 1
            else:
                end = mid - 1

complexity

时间复杂度O(lgn)

空间复杂度O(1)

[yj9676]

class Solution {
    public int mySqrt(int x) {
        if (x == 0) {
            return 0;
        }
        int ans = (int) Math.exp(0.5 * Math.log(x));
        return (long) (ans + 1) * (ans + 1) <= x ? ans + 1 : ans;
    }
}

[bolunzhang2021]

LC69

自己做的：超时

class Solution {
    public int mySqrt(int x) {
         int n=0;
        for(; n<=x;n++){
            if(n*n==x)
                return n;
            else if(n*n>x)
                return n-1;
            else if(n*n<x)
                continue;
        }
        return -1;
    }
}

-参考题解，二分

class Solution {
    public int mySqrt(int x) {
          long left = 0;
                long right = x;
                while (left <= right) {
                    long mid = left + (right - left) / 2;
                    if (mid*mid <= x) {
                        // 搜索区间变为 [mid+1, right]
                        left = mid + 1;
                    }
                    if (mid*mid> x) {
                        // 搜索区间变为 [left, mid-1]
                        right = mid - 1;
                    }
                }
                // 检查是否越界
                if (right < 0 || right*right> x)
                    return -1;
                return (int)right;
    }
}

时间复杂度O(lgn)

空间复杂度O(1)

[ZacheryCao]

Idea:

Binary search. Initialize left and right pointer as 0 and x. Mid = left + (right - left + 1) //2. If Mid * Mid > x, right = Mid - 1. Else left = Mid

Code

class Solution:
    def mySqrt(self, x: int) -> int:
        l, r = 0, x
        while l < r:
            mid = l + (r - l + 1)//2
            if mid * mid > x:
                r = mid -1
            else:
                l = mid
        return l

Complexity:

Time: O(log n). n = x Space: O(1)

[ZiyangZ]

class Solution {
    public int mySqrt(int x) {
        if (x == 0 || x == 1) return x;
        int left = 0;
        int right = x;
        while (left <= right) {
            int mid = left + (right - left) / 2; // prevent overflow
            long sq = (long) mid * mid;
            if (sq == x) return mid;
            if (sq < x) left = mid + 1;
            else right = mid - 1;
        }
        return right;
    }
}

[erik7777777]

class Solution {
    public int mySqrt(int x) {
        if (x < 2) return x;
        int left = 1;
        int right = x / 2;
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            if (mid > x / mid) {
                right = mid - 1;
            } else {
                left = mid;
            }
        }
        return left;
    }
}

Binary Search Time O(logn) SpaceO(1)

[Moin-Jer]

思路

---

寻找最右边满足条件的值

代码

---

class Solution {
    public int mySqrt(int x) {
        int l = 0, r = x;
        while (l <= r) {
            int mid = (l + r) >>> 1;
            if ((long)mid * mid <= x) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return r;
    }
}

复杂度分析

---

• 时间复杂度：O（logx）
• 空间复杂度：O（1）

[learning-go123]

思路

• 二分

代码

• 语言支持：Go

Go Code:

func mySqrt(x int) int {
    l,r := 0, x
    for l <= r {
        mid := (r-l)/2 + l
        if mid * mid == x {
            return mid
        } else if mid*mid < x {
            l = mid + 1
        } else {
            r = mid - 1
        }
    }
    return l - 1
}

复杂度分析

令 n 为数组长度。

• 时间复杂度：$O(logn)$
• 空间复杂度：$O(1)$

[freedom0123]

class Solution {
    public int mySqrt(int x) {
        long l = 0;
        long r = x;
        while(l<r){
            long mid  = l+r+1l>>1;
            if(mid <= x/mid){
                l = mid;
            }else{
                r = mid-1;
            }
        }
        return (int)l;
    }
}

[joeytor]

思路

查找最大的符合 i ^2 ≤ x 的值

使用 查找 最右边的满足条件的值 (i^2 ≤ x)

​ 如果 mid**2 < x, 那么 l = mid + 1 查找右边

​ 如果 mid**2 > x, 那么 r = mid - 1 查找左边

​ 如果 mid**2 == x, 那么 mid 就是要找到数, 返回 mid

最后返回 r 因为是最大的满足 i^2 ≤x 的值

class Solution:
    def mySqrt(self, x: int) -> int:
        l, r = 0, x

        while l <= r:
            mid = (l+r) >> 1
            if mid * mid < x:
                l = mid + 1
            if mid * mid > x:
                r = mid - 1
            if mid * mid == x:
                return mid

        return r

复杂度

时间复杂度: O(logx) 二分查找的时间复杂度

空间复杂度: O(1)

[Toms-BigData]

【Day 37】69. x 的平方根

思路

二分查找

Python3代码

class Solution:
    def mySqrt(self, x: int) -> int:
        if x == 1:
            return 1
        head = 0
        tail = x
        mid = int((head + tail)/2)
        while not (mid*mid<=x and (mid+1) * (mid+1) > x):
            if mid * mid > x:
                tail = mid
                mid = int((head + tail)/2)
            else:
                head = mid
                mid = int((head + tail) / 2)

        return int(mid)

复杂度

时间:O(log2n) 空间:O(1)

[yingliucreates]

link:

https://leetcode.com/problems/sqrtx/

代码 Javascript

const mySqrt = function (x) {
  let lo = 0,
    hi = x;
  while (lo <= hi) {
    const mid = parseInt((lo + hi) / 2);
    if (mid * mid === x) {
      return mid;
    }
    if (x < mid * mid) {
      hi = mid - 1;
    } else {
      lo = mid + 1;
    }
  }
  return hi;
};

复杂度分析

time: O(logn) space: O(1)

[tongxw]

思路

用x/mid防止溢出，判断mid = 0也就是 x = 0和1的例外情况 由于 sqrt(8) = 2而不是3，所以最后的左右指针，要取右指针返回答案 (最后r + 1 = l)

代码

class Solution {
    public int mySqrt(int x) {
        if (x == 0) {
            return 0;
        }
        if (x == 1) {
            return 1;
        }

        int left = 0;
        int right = x;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (mid == x / mid) {
                return mid;
            } else if (mid > x / mid) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        return right;
    }
}

TC: O(logx) SC: O(1)