求平方根

[编程题]求平方根

热度指数：158010 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

实现函数 int mysqrt(int x).

计算并返回 x 的平方根（向下取整）

数据范围： $0 <= x < 2^{31}-1$

要求：空间复杂度 $O(1)$ ，时间复杂度 $O(logx)$

示例1

输入

输出

示例2

输入

2143195649

输出

算法知识视频讲解

查看答案及解析

Python3

Joy_9

class Solution:
    def mysqrt(self , x: int) -> int:
        # write code here
        left=0
        right=x
        
        while left<=right:
            root=(left+right)//2
            if root*root<x:
                if (root+1)*(root+1)<x:
                    left=root+1
                elif (root+1)*(root+1)==x:
                    return root+1
                elif (root+1)*(root+1)>x:
                    return root
            elif root*root>x:
                if (root-1)*(root-1)>x:
                    right=root-1
                elif (root-1)*(root-1)==x:
                    return root-1
                elif (root-1)*(root-1)<x:
                    return root-1
            elif root*root==x:
                return root

发表于 2021-12-30 03:07:21 回复(0)

Python3

ZirconiumZr

class Solution:
    def mysqrt(self , x: int) -> int:
        if x == 0:
            return 0
        elif x == 1:
            return 1
        else:
            i=0
            while i*i <= x:
                i+=1
            return(i-1)

发表于 2021-12-11 17:01:26 回复(0)

Python3

rebecca2021

class Solution:
    def mysqrt(self , x ):
        # write code here
        if x==0:
            return 0
        if x==1:
            return 1
        if x ==2:
            return 1
        else:
            lower = 0
            ans = 0
            upper = x
            while True:
                mid = (upper - lower) // 2 + lower
                if mid * mid <= x:
                    if (mid + 1) * (mid + 1) > x:
                        ans = mid
                        return ans
                    else:
                        lower = mid
                else:
                    upper = mid

mark

发表于 2021-10-13 12:28:57 回复(0)

Python3

王钲超

#
#
# @param x int整型
# @return int整型
#
import math
class Solution:
def mysqrt(self , x ):
# write code here
return math.floor(math.mysqrt(x))

发表于 2021-07-25 16:16:33 回复(5)

Python3

不愿吃饼的三文鱼很调皮

class Solution:
    # 二分法
    def mysqrt(self, x):
        if x < 2: return x
        i, j = 1, x // 2
        last = 0
        while i <= j:
            mid = i + (j - i) // 2
            if x // mid < mid:
                j = mid - 1
                
            elif x // mid > mid:
                i = mid + 1
                last = mid
            else:
                return mid
        return last
    
    # 直接返回平方根，向下取整
    def mysqrt2(self , x ):
        return int(x**0.5)
    
    # 奇数相加一定是平方数
    def mysqrt3(self , x ):
        res = 0
        begin = 1
        while x >= 0:
            x -= begin
            res += 1
            begin += 2
        return res-1

发表于 2021-07-18 08:36:53 回复(0)