Solution 1 is straightforward. Solution 2 uses binary search. Solution 3 uses Newton’s Iteration.
Solution 1
class Solution:
def mySqrt(self, x: int) -> int:
i = 0
while x >= i*i:
i += 1
return i - 1
Time complexity is O(n). Space complexity is O(1).
Solution 2
class Solution:
def mySqrt(self, x: int) -> int:
if x < 2: return x
left, right = 1, x // 2
while left <= right:
mid = left + (right - left) // 2
if x < mid*mid:
right = mid - 1
else: left = mid + 1
return left - 1
Time complexity is O(logn). Space complexity is O(1).
Solution 3
class Solution:
def mySqrt(self, x: int) -> int:
return int(x**0.5)
Time complexity is O(1). Space complexity is O(1).
Solution 4
class Solution:
def mySqrt(self, x: int) -> int:
x_previous = x
x_current = x / 2
precision = 0.1
while abs(x_previous - x_current) > precision:
x_previous = x_current
x_current = (1/2) * (x_current + x/x_current)
return int(x_current)
Time complexity is O(logn). Space complexity is O(1).
步步发财 