0069. x 的平方根

0069. x 的平方根 #

  • 标签:数学、二分查找
  • 难度:简单

题目大意 #

实现 int sqrt(int x) 函数。计算并返回 x 的平方根(只保留整数部分),其中 x 是非负整数。

解题思路 #

因为求解的是 x 开方的整数部分。所以我们可以从 0~x 的范围进行遍历,找到 k^2 <= x 的最大结果。

为了减少时间复杂度,使用二分查找的方式来搜索答案。

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def mySqrt(self, x: int) -> int:
        left = 0
        right = x
        ans = -1
        while left <= right:
            mid = (left+right)//2
            if mid*mid <= x:
                ans = mid
                left = mid+1
            else:
                right = mid-1
        return ans
本站总访问量  次  |  您是本站第  位访问者