【Day 37 】2022-01-17 - 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..., 由于返回类型是整数，小数部分将被舍去

[yan0327]

思路： 1.二分法找大概值。这里注意一个细节，如果大则r = mid -1 2.小的话记得先临时存储当前值，在l = mid+1 [因为l右移后可能会导致不符合情况] 以上是区别与其他情况的地方

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

时间复杂度O（NlogN） 空间复杂度O（N）

[bluetomlee]

// 二分搜索，在匹配

class Solution {

public:

int mySqrt(int x) {

int left = 0, right = x;

// 边界情况

if (x <= 1) {

return x;

}

while(left < right) {

int middle = (left + right) / 2;

// 不能 x >= middl，会导致eoverflow了

if (x / middle >= middle) {

left = middle + 1;

} else {

right = middle;

}

}

return right - 1;

}

};

[zwx0641]

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

    int l = 1, r = x, mid = 0, sqrt = 0;

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

        if (sqrt == mid) {
            return sqrt;
        } else if (mid < sqrt) {
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    return r;
}

}

[zjsuper]

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

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

···

[ZacheryCao]

Idea

Binary Search

Code

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

Complexity:

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

[Brent-Liu]

public class Solution {

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

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

}

[zwang2244]

思路

find the num using binary search

代码

class Solution {
    public int mySqrt(int x) {
        if(x < 2) return x;

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

复杂度分析

• 时间复杂度：O(logN)，其中 N 为数组长度。
• 空间复杂度：O(1)

[cszys888]

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

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

[moirobinzhang]

Code:

public class Solution { public int MySqrt(int x) { if ( x <= 1) return x;

    int left = 0;
    int right = x;

    while(left <= right)
    {
        int mid = ( right - left ) / 2 + left;
        int sqrt = x / mid;

        if (mid  == sqrt)
            return mid;

        if (mid > sqrt)
            right = mid - 1;
        else
            left = mid + 1;

    }

    return right;        
}

}

[zwmanman]

class Solution(object): def mySqrt(self, x): """ :type x: int :rtype: int """

    l = 0
    r = x

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

    return ans

[CodeWithIris]

Day37 69

Note

Solution (C++)

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

Complexity

• T: O(logn)
• S: O(1)

[freesan44]

思路

二分法

关键点

代码

• 语言支持：Python3

Python3 Code:

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

复杂度分析

令 n 为数组长度。

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

[rzhao010]

Thoughts Binary search

Code

    public int mySqrt(int x) {
        if (x < 2) {
            return x;
        }

        int start = 1, end = x;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (x / mid == mid) {
                return mid;
            } else if (x / mid > mid) {
                start = mid;
            } else {
                end = mid;
            }
        }
        if (x /end >= end) {
            return end;
        } else {
            return start;
        }
    }

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

[YuyingLiu2021]

class Solution:
    def mySqrt(self, x: int) -> int:
        if x <= 1:
            return x
        if ( x > 0 and x <= 2**31 -1):
            for i in range(2**31 -1):
                if i*i == x:
                    return i
                else:
                    if i*i < x and (i+1)*(i+1) >x:
                        return i

[ZhangNN2018]

class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        i=1
        while True:
            if i*i > x:
                return i-1
            i = i + 1

[Tesla-1i]

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

[phybrain]

思路

二分

代码

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)

复杂度分析

• 时间复杂度：O(logN)，其中 N 为数组长度。
• 空间复杂度：O(1)

[nonevsnull]

思路

//s6

• 思路与解法

• 二分就是模版
• 最右小于target的位置+1；
• 因为这里要处理2^2~=8这种情况，所以小于和等于分别处理一下；

代码

//s6
class Solution {
    public int mySqrt(int x) {
        if(x == 0) return x;
        int left = 1, right = x;

        while(left <= right){
            int mid = left + (right - left) / 2;

            if(mid > x / mid){
                right = mid - 1;
            } else if( mid == x / mid) {
                return mid;
            } 
            else {
                left = mid + 1;
            }
        }
        return left-1;
    }
}

复杂度

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

[hdyhdy]

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

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

[Zhang6260]

JAVA版本

这题是最经典的二分法了，需要注意的是如果使用乘法的话可能会出现越界的问题，可以将乘法转换为除法。

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

时间复杂度：O(logn)

空间复杂度：O(1）

[Yark-yao]

思路

找到一个足够小的合适区间[begin,end]，使得beginbegin<=x , endend >=x ，然后遍历begin至end

代码

function mySqrt(x: number): number {
    // 找到一个区间
    if(x === 0){
        return 0
    }
    if(x === 1){
        return 1
    }

    let base = x >> 1;
    let nextBase = base >> 1
    while(base*base > x){
        if(nextBase*nextBase <=x){
            break
        }
        base = base >> 1
        nextBase = base >> 1
    }
    for(let i = nextBase;i<=base-1;i++){
        if( i * i <= x && (i+1)*(i+1) > x){
            return i
        }
    }
    return base
};

复杂度

时间: O(logx)，二分查找需要的次数 空间：O(1)

[Serena9]

代码

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

复杂度分析

时间复杂度：O(log x）

空间复杂度：O(1)

[xinhaoyi]

69. x 的平方根

题目

实现 int sqrt(int x) 函数。

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

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

示例 1:

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

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

思路

使用牛顿迭代法，先求出开方后根的大小，再进行取整

代码

//使用牛顿迭代法，先求出开方后根的大小，再进行取整
class Solution {
    public int mySqrt(int x) {
        double err = 1e-15;
        //这里一定不要偷工减料，否则一定会在数字比较大的时候出错
        //double err = 0.1;
        double t = x;
        while(Math.abs(t - x/t) > err*t){
            t = (x/t + t)/2.0;
        }
        return (int)t;
    }
}

复杂度分析

时间复杂度 $o(n)$

空间复杂度$o(1)$

[callmeerika]

思路

二分查找

代码

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

复杂度

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

[tangjy149]

思路

牛顿迭代法，通过不断迭代进行逼近正确值

代码

class Solution {
public:
    int mySqrt(int x) {
        double e=1e-10;
        double a=x;
        double b=(a+x/a)/2;
        while(abs(a-b)>e){
            a=b;
            b=(a+x/a)/2;
        }
        return a;
    }
};

[xuhzyy]

思路

二分法

代码

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

复杂度分析

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

[feifan-bai]

思路

1. 二分查找缩小区间

代码

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

复杂度分析

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

[shamworld]

var mySqrt = function(x) {
    var left = 0,right = x,result = -1;
    while(left<=right){
        let mid = Math.floor(left+(right-left)/2);
        if(mid*mid==x) return  mid;
        //小了 所以在右边
        if(mid*mid<x){ 
            left = mid+1;
            //有可能mid*mid==x永远都不相等 所以这个地方要先赋值给result
            result = mid;
        }
        if(mid*mid>x){
            right = mid-1;
        }
    }
    return result;
};

[iambigchen]

思路

当前值的平方小于等于x，当前值+1的平方大于x。则当前值就是我们要找的值

关键点

代码

• 语言支持：JavaScript

JavaScript Code:

/**
 * @param {number} x
 * @return {number}
 */
var mySqrt = function(x) {
    let l = 0
    while(l <= x) {
        if (l ** 2 <= x && (l + 1) ** 2 > x) {
            return l
        }
        l++
    }
};

复杂度分析

令 n 为数组长度。

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

思路2

相当于找数组最右边符合目标值，而目标值就是x，数组则是从0到x的整数数组。

关键点

代码

• 语言支持：JavaScript

JavaScript Code:

/**
 * @param {number} x
 * @return {number}
 */
var mySqrt = function(x) {
    let l = 0
    let r = x
    while(l <= r) {
        let mid = (l + r) >> 1
        if (mid ** 2 > x) {
            r = mid - 1
        }
        if (mid ** 2 <= x) {
            l = mid + 1
        }
    }
    return r
};

复杂度分析

令 n 为数组长度。

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

[Toms-BigData]

【Day 37】69. x 的平方根

思路

二分法

golang代码

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

复杂度

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

[wenlong201807]

代码块

var mySqrt = function(x) {
  if (x == 0) return 0

  let left = 1
  let right = Math.floor(x / 2)

  while (left < right) {
    let mid = Math.ceil((left + right) / 2) 
    if (mid > x / mid) {
      right = mid-1
    } else {
      left = mid
    }
  }

  return Math.floor(left)
};

时间复杂度和空间复杂度

• 时间复杂度 O(n)
• 空间复杂度 O(1)

[charlestang]

思路

因为非负数的平方根是单调的。所以可以使用二分查找。

代码

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

时间复杂度 O(logn)

[testeducative]

思路

二分法

代码

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

[Yachen-Guo]

思路

简单题，二分法。要注意数据的溢出。

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

[Flower-F]

解法分析

二分

代码

/**
 * @param {number} x
 * @return {number}
 */
var mySqrt = function(x) {
    let left = 0, right = x;
    let targetIndex;

    while (left <= right) {
        const mid  = (left + right) >> 1;
        if (mid * mid <= x) {
            // 满足条件
            // 找的是最右的满足条件的元素，所以是收缩左边界
            left = mid + 1;
            targetIndex = mid;
        } else {
            right = mid - 1;
        }
    }

    return targetIndex;
};

复杂度

时间：O(logN) 空间：O(1)

[chengyufeng6]

class Solution { public: int mySqrt(int x) { double right = x; double left = 0; double mid = 0; long long temp = 0; for(;temp != x;) { mid = (right + left) / 2; temp = mid * mid; if(temp > x) { right = mid; } else if(temp < x) { left = mid; } } return mid; } };

[laofuWF]

# binary search, return right pointer

# time: O(logN)
# space: O(1)
class Solution:
    def mySqrt(self, x: int) -> int:
        if x < 2:
            return x

        left = 0
        right = x // 2

        while left <= right:
            mid = left + (right - left) // 2

            if mid * mid == x:
                return mid

            # keep mid since mid could be our ans
            if mid * mid < x:
                left = mid + 1
            else:
                right = mid - 1

        return right

[wangzehan123]

代码

• 语言支持：Java

Java Code:

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

[Menglin-l]

approach: binary search

---

code:

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

---

complexity:

Time: O(logN)

Space: O(1)

[anyingbinglong]

思路： 1.二分法找大概值。这里注意一个细节，如果大则r = mid -1 2.小的话记得先临时存储当前值，在l = mid+1 [因为l右移后可能会导致不符合情况] 以上是区别与其他情况的地方

func mySqrt(x int) int { l,r := 0,x out:=0 for l <= r{ mid := l + (r-l)/2 if mid*mid > x{ r = mid-1 }else{ out = mid l = mid+1 } } return out } 时间复杂度O（NlogN） 空间复杂度O（N）

[ZJP1483469269]

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

        return r

[LinnSky]

思路

二分法

代码

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

复杂度分析

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

[tongxw]

思路

二分查找，找不到的时候返回下界

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

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

        return r;
    }
}

TC: O(logN) SC: O(1)

[zhangzz2015]

• 采用二分方法，注意int溢出问题。时间复杂度为O(logn)，空间复杂度为O(1)。

关键点

代码

• 语言支持：C++

C++ Code:

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

        int left =0; 
        int right = x/2+1; 
        while(left<=right)
        {
            int middle = left + (right -left)/2; 

            long long total = (long long)(middle)*middle; 
            if(total ==x)
                return middle;
            else if(total < x)
                left = middle+1; 
            else
                right = middle-1;                        
        }

        // [right left]

        return right; 

    }
};

[herbertpan]

思路

1. 思路并不复杂就是二分法
2. 复杂在于如何处理overflow而不使用long/double

3. overflow的解决方案就是 x * x > Integer.MAX_VALUE ==> x > Integer.MAX_VALUE / x

   code

   class Solution {
   public int mySqrt(int x) {
       if (x == 0 || x == 1)  {
           return x;
       }
   
       int left = 1;
       int right = x / 2;
       while (left + 1 < right) {
           int mid = left + (right - left) / 2;
   
           // overflow?
           if (mid > Integer.MAX_VALUE / mid) {
               right = mid - 1;
           } else {
               int temp = mid * mid;
               if (temp == x) {
                   return mid;
               } else if (temp > x) {
                   right = mid - 1;
               } else {
                   left = mid;
               }
           }
       }
   
       // only left and right
       if (right <= Integer.MAX_VALUE / right && right * right <= x) {
           return right;
       } else {
           return left;
       }
   }
   }

complexity

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

[LannyX]

思路

二分

代码

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

复杂度分析

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

[junbuer]

思路

• 二分法

  代码

  
  class Solution(object):
  def mySqrt(self, x):
      """
      :type x: int
      :rtype: int
      """
      l, r = 0 ,x
      while l <= r:
          mid = (l + r) >> 1
          if mid * mid <= x:
              ans = mid
              l = mid + 1
          else:
              r = mid - 1
      return ans

### 复杂度分析
+ 时间复杂度：$O(logn)$
+ 空间复杂度：$O(1)$

[didiyang4759]

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

[Hacker90]

思路

二分法 对于一个非负数n，它的平方根不会大于n/2+1

代码

class Solution {
public:
    int mySqrt(int x) {
         long long i = 0;
         long long j = x/2+1;
         while(i<=j){
             long long mid = (i+j)/2;//对于一个非负数n，它的平方根不会大于n/2+1
             long long res = mid*mid;
             if(res == x)return mid;
             else if(x > res)i = mid + 1;
             else
                j = mid -1;
         }
         return j;     
    }
};

复杂度分析

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

[xiao-xiao-meng-xiang-jia]

class Solution { public int mySqrt(int x) { int n =0; n = (int) Math.sqrt(x); return n; } }