69. Sqrt(x)

题目描述和难度

• 题目描述：

输入: 4

输出: 2

输入: 8

输出: 2

说明: 8 的平方根是 2.82842..., 

     由于返回类型是整数，小数部分将被舍去。

• 题目难度：简单。
• 英文网址：69. Sqrt(x) 。
• 中文网址：69. x 的平方根 。

思路分析

求解关键：

参考解答

参考解答1：使用二分查找，特别注意：应该返回右边端点。

class Solution:
    # 二分法
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        l = 0
        r = x // 2 + 1
        while l <= r:
            m = l + (r - l) // 2
            s = m * m
            if s == x:
                return m
            elif s < x:
                l = m + 1
            else:
                r = m - 1
        # 注意返回 l 和返回 r 的区别，应该返回 r
        # 【因为返回的是不超过，所要把右边界返回回去】
        return r

class Solution:
    # 二分法
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        if x == 1:
            return 1
        l = 0
        r = x // 2
        while l <= r:
            m = l + (r - l) // 2
            s = m * m
            if s == x:
                return m
            elif s < x:
                l = m + 1
            else:
                r = m - 1
        return r

参考解答2：使用牛顿法，我个人比较推荐牛顿法，更简单，返回值向下取整，就能符合题要求。

class Solution:
    # 牛顿法
    # 与系统函数作比较

    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        if x < 0:
            raise Exception('不能输入负数')
        if x == 0:
            return 0

        cur = 1
        while True:
            pre = cur
            cur = (cur + x / cur) / 2
            if abs(cur - pre) < 1e-6:
                return cur

    # 这个解直接提交到 LeetCode 上就可以了
    def mySqrt1(self, x):
        """
        :type x: int
        :rtype: int
        """
        if x < 0:
            raise Exception('不能输入负数')
        if x == 0:
            return 0
        # 起始的时候在 1 ，这可以比较随意设置
        cur = 1
        while True:
            pre = cur
            cur = (cur + x / cur) / 2
            if abs(cur - pre) < 1e-6:
                return int(cur)


if __name__ == '__main__':
    import numpy as np

    nums = np.linspace(0, 999, 100)
    solution = Solution()
    for num in nums:
        a = solution.mySqrt(num)
        b = np.sqrt(num)
        print("牛顿法：{} \t NumPy：{}\t 差距：{}".format(a, b, a - b))