leetcode69:x的平方根

原题地址：69. x 的平方根 - 力扣（LeetCode）

题目描述

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

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

注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

示例 1：

输入：x = 4
输出：2

示例 2：

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

解题思路

解题的核心思想是利用对数的性质来快速逼近平方根的值。我们知道 �=�2x=y2，则 �=�x​=y。通过对 �x 取对数，我们可以得到 log⁡(�)=2log⁡(�)log(x)=2log(y)，从而 log⁡(�)=12log⁡(�)log(y)=21​log(x)。通过对两边取指数，我们可以得到 �=�12log⁡(�)y=e21​log(x)，这就是代码中 Math.exp(0.5 * Math.log(x)) 的部分。

接下来，我们需要检查这个值是否是 �x 的平方根。如果 (���+1)2≤�(ans+1)2≤x，则 ���+1ans+1 是一个更接近的平方根；否则，���ans 就是 �x 的平方根。

源码实现

class Solution {public int mySqrt(int x) {// 如果x为0，直接返回0，因为0的平方根是0if (x == 0) {return 0;}// 使用对数和指数的性质来计算x的平方根的近似值int ans = (int) Math.exp(0.5 * Math.log(x));// 检查(ans + 1)的平方是否小于等于x，如果是，则ans + 1是x的平方根// 否则，ans就是x的平方根return (long) (ans + 1) * (ans + 1) <= x ? ans + 1 : ans;}
}

复杂度分析

• 时间复杂度：O(1)。虽然代码中使用了对数和指数函数，但这些操作的时间复杂度可以认为是常数级别的，因为它们不需要迭代或递归。因此，整个算法的时间复杂度是常数级别的。

• 空间复杂度：O(1)。算法中没有使用额外的数据结构来存储数据，除了几个变量，所以空间复杂度也是常数级别的。