LeetCode.069.Sqrt(x) x的平方根

题目描述

69 Sqrt(x)
https://leetcode-cn.com/problems/sqrtx/

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.

---

相似题目

LeetCode.剑指offer.064.计算1到n的和

LeetCode.371.Sum of Two Integers 不用加减号计算整数加法

LeetCode.069.Sqrt(x) x的平方根
LeetCode.050.Pow(x,n) 实现Pow(x,n)

---

解题过程

二分搜索

二分搜索 0 到 x 闭区间内的所有整数，x 的平方根肯定在此区间内
时间复杂度 O(logn)，空间复杂度 O(1)

// 二分搜索
private static class SolutionV2020BinarySearch {
    public int mySqrt(int x) {
        int low = 0, high = x;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (Math.pow(mid, 2) == x) {
                return mid;
            } else if (Math.pow(mid + 1, 2) == x) {
                return mid + 1;
            } else if (Math.pow(mid, 2) < x && Math.pow(mid + 1, 2) > x) {
                return mid;
            } else if (Math.pow(mid, 2) < x) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return 0;
    }
}

指数对数公式变换

既然是实现 sqrt(x)，肯定不能用库函数中的 Math.sqrt(x) 了，但没说不能用库函数中的其他幂函数或对数函数
根据数学公式，把 x 的平方根变换为 自然对数 和 e 的幂函数。

$ \sqrt{x} = x^{\frac{1}{2}} = (e^{\ln x})^{\frac{1}{2}} = e^{\frac{1}{2} \ln x} $

但这样算出来会有误差，需要比较结果 res 和 res+1 哪个是正确的

牛顿迭代法

---

GitHub代码

algorithms/leetcode/leetcode/_069_Sqrtx.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_069_Sqrtx.java

---