难度: Easy
原题连接
内容描述
Implement int sqrt(int x).
Compute and return the square root of x, where x is guaranteed to be a non-negative integer.
Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.
Example 1:
Input: 4
Output: 2
Example 2:
Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since
the decimal part is truncated, 2 is returned.
思路 1 - 时间复杂度: O(lgN)- 空间复杂度: O(1)******
一看，觉得很容易，一写，超时：
class Solution(object):
def mySqrt(self, x):
"""
:type x: int
:rtype: int
"""
i = 0
while i * i <= x:
if i * i <= x and (i + 1) * (i + 1) > x:
return i
i += 1
思路 2 - 时间复杂度: O(lgN)- 空间复杂度: O(1)******
二分
class Solution(object):
def mySqrt(self, x):
"""
:type x: int
:rtype: int
"""
if x == 0:
return 0
if x == 1:
return 1
l, r = 0, x - 1
while l <= r:
mid = l + ((r-l) >> 1)
if mid * mid <= x and (mid+1) * (mid+1) > x:
return mid
elif mid * mid > x:
r = mid - 1 # 这里也可以 r = mid
else:
l = mid + 1思路 3 - 时间复杂度: O(lgN)- 空间复杂度: O(1)******
跟思路 2 一样，就是return时机不一样
class Solution(object):
def mySqrt(self, x):
"""
:type x: int
:rtype: int
"""
if x == 1:
return 1
if x == 0:
return 0
l, r = 0, x-1
while l <= r:
mid = l + ((r - l) >> 2)
if (mid * mid - x == 0):
return mid
elif (mid * mid - x > 0):
r = mid - 1
else:
l = mid + 1
return r思路 4 - 时间复杂度: O(lgN)- 空间复杂度: O(1)******
话说还想到求sqrt有个🐂的牛顿法？
class Solution(object):
def mySqrt(self, x):
"""
:type x: int
:rtype: int
"""
t = x
while t * t > x:
t = (t + x / t) / 2
return t