LEETCODE 69. Sqrt(x) 解题思路分析

题目大意:

x 的平方根

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根,其中 x 是非负整数。

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

示例 1:

输入: 4
输出: 2

示例 2:

输入: 8
输出: 2
说明: 8 的平方根是 2.82842..., 
     由于返回类型是整数,小数部分将被舍去。

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=69

解题思路分析:

本题的暴力解法是从1到x分别求平方,找到第一个小于等于x的数即可。这样的线性解法时间复杂度为x,如果x非常大的话,效率会很低。因此这类题目需要考虑使用二分查找,查看1和x的中间数mid的平方n,如果n等于x,那么返回mid。如果n小于x并且mid加一的平方大于x,这时也可以返回mid。除此之外,如果n小于x,左指针变为mid加一,反之右指针变为mid-1。

实现代码:

public int mySqrt(int x) {
    if(x<=1) return x;
    long l=1,r=x;
    while(l<=r){
        long mid=(l+r)/2;
        long n=mid*mid;
        if(n==x||n<x&&(mid+1)*(mid+1)>x) return (int)mid;
        if(n>x){
            r=(int)mid-1;
        }else{
            l=(int)mid+1;
        }
    }
    return -1;
}

本题解法执行时间为1ms。

Runtime: 1 ms, faster than 100.00% of Java online submissions for Sqrt(x).

Memory Usage: 37 MB, less than 5.00% of Java online submissions for Sqrt(x).

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: https://leetcode.jp/leetcode-69-sqrtx-解题思路分析/
此条目发表在leetcode分类目录,贴了, , , 标签。将固定链接加入收藏夹。

发表评论

电子邮件地址不会被公开。