当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.069.Sqrt(x) x的平方根

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.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


上一篇 LeetCode.050.Pow(x,n) 实现Pow(x,n)

下一篇 LeetCode.221.Maximal Square 最大正方形

阅读
评论
382
阅读预计2分钟
创建日期 2020-05-09
修改日期 2020-05-09
类别

页面信息

location:
protocol:
host:
hostname:
origin:
pathname:
href:
document:
referrer:
navigator:
platform:
userAgent:

评论