Description
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.
Solutions
实现开方的功能，舍去小数部分，只保留整数。
1. Binary Search - 迭代
注意最后的结果是 left，还要减 1。
# Time: O(n)
# Space: O(1)
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
center = x / mid
if mid == center:
return mid
elif mid > center:
right = mid - 1
else:
left = mid + 1
return left - 1
# 1017/1017 cases passed (28 ms)
# Your runtime beats 90.13 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (12.6 MB)
当然也可以在更新left时，就不用 mid 加 1，这样最后的结果就不用加 1。同样也可以直接返回 right，这样也不用考虑加 1 的问题。
# Time: O(n)
# Space: O(1)
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
x_cmp = mid ** 2
if x_cmp == x:
return mid
elif x_cmp > x:
right = mid - 1
else:
left = mid + 1
return right
# 1017/1017 cases passed (28 ms)
# Your runtime beats 90.13 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (12.6 MB)
2. Binary Search - 递归
class Solution(object):
def binary_search(self, l, r, x):
mid = (l + r) / 2
mid_p = mid ** 2
if mid_p == x:
return mid
elif mid_p < x:
if (mid + 1) ** 2 > x:
return mid
else:
return self.binary_search(mid, r, x)
else:
return self.binary_search(l, mid, x)
def mySqrt(self, x):
"""
:type x: int
:rtype: int
"""
if x == 1:
return 1
return self.binary_search(0, x, x)
# Runtime: 28 ms, faster than 51.77% of Python online submissions for Sqrt(x).
# Memory Usage: 11.8 MB, less than 29.96% of Python online submissions for Sqrt(x).