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).

References

  1. 69. Sqrt(x)