ACM 选手图解 LeetCode 算术平方根

大家好呀，我是你们的算术蛋。

今天解决算术平方根 Sqrt(x)，通过这道常见面试题作为二分查找实战系列开篇。

咱们话不多说，赶紧开整。

   LeetCode 69：Sqrt(x)

题意

给一个非负整数 x，计算并返回 x 的算术平方根。

返回类型是整数，结果只保留小数部分，小数部分被舍去。

示例

输入：x = 8

输出：2

解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。

提示

• 不允许使用任何内置指数函数和算符    
  
• 0 <= x <= 2^31 -1
  

题目解析

水题，难度简单，面试中的常见题。

这道题当然不能使用 pow(x, 0.5) 或 x ** 0.5 等内置函数，不然就没了考察的意义。

对于本题，是对非负整数 x 开根号，即 y = sqrt(x)，

这是一个单调递增函数。

而我在【ACM 选手带你玩转二分查找！】文章中讲过，二分查找的使用，要有一个前提条件：要查找的数必须在一个有序数组里。

这道题的条件正好满足单调递增，并且 sqrt(x) 返回的是整数 res，而 res 是满足 res * res <= x 的最大值，所以可以用二分查找来解决。

明白了这些剩下的就是常规操作：

• 确定二分查找的上界 high = x 和下界 low = 0。
  
• 比较 mid * mid 与 x 的关系，动态调整 [low, high]。
  
  

图解

以 n = 8 为例，为了方便大家理解，我把从 low ~ high 之间所有的数都列出来。

low, high, res = 1, x, -1

第 1 步，x = 8，low = 1，high = 8，mid = (low + high) // 2 = 4：

mid = (low + high) // 2

此时 mid * mid = 16 > x，则 high 向左移动至 mid - 1 = 3 处。

if mid * mid > x:
      high = mid - 1

第 2 步，x = 8，low = 1，high = 3，mid = (low + high) // 2 = 2：

此时 mid * mid = 4 <= x，则 res = mid = 2，low 向右移动至 mid + 1 = 3 处

if mid * mid <= x:
    res = mid
    low = mid + 1

第 3 步，x = 8，low = 3，high = 3，mid = (low + high) // 2 = 3：

此时 mid * mid = 9 > x，则 high 向左移动至 mid - 1 = 2 处。

此时 low > high，循环终止，输出 res = 2。

本题题解使用二分查找 res，查找的长度为 x，所以时间复杂度为 O(logx)。

额外创建了 low、high 指针及 res 存储结果，所以空间复杂度为 O(1)。

代码实现

Python 代码实现

class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        if x == 0 or x == 1:
            return x
        low, high, res = 1, x, -1
        while low <= high:
            mid = (low + high) // 2
            if mid * mid <= x:
                res = mid
                low = mid + 1
            else:
                high = mid - 1
        return res

Java 代码实现

class Solution {
    public int mySqrt(int x) {
        int low = 0, high = x, res = -1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if ((long) mid * mid <= x) {
                res = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return res;
    }

图解 Sqrt(x) 到这就结束辣，看了之后是不是觉得还挺简单的？

不过，上一篇文章我讲了二分查找，看到这道题的时候你有第一反应用二分查找去解决嘛？

AC 不是目的，目的是好好去琢磨琢磨这种解题方法，然后能运用到之后的题目中。

有问题可以留言区留言，记得帮我点赞在看呀，么么哒。

我是帅蛋，我们下次见。