【小Y学算法】⚡️每日LeetCode打卡⚡️——21.x 的平方根

呆呆敲代码的小Y

发布于 2021-09-06 14:35:24

2840

发布于 2021-09-06 14:35:24

文章被收录于专栏：呆呆敲代码的小Y 公众号

前言

每天打卡一道算法题，既是一个学习过程，又是一个分享的过程
提示：本专栏解题编程语言一律使用 C# 和 Java 两种进行解题
要保持一个每天都在学习的状态，让我们一起努力成为算法大神吧！
今天是力扣算法题持续打卡第21天！

原题样例

实现int sqrt(int x)函数。

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

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

示例 1:

输入: 4
输出: 2

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

C#方法：二分查找

思路解析

根据题意我们知道，最终目的就是返回 x 的平方根

我们可以直接调用Sqrt方法找到平方根，但是这就不是算法的本意啦~

所以可以使用二分法来解决这个问题

二分查找的下界为 0，上界可以粗略地设定为 x。

在二分查找的每一步中，我们只需要比较中间元素 mid 的平方与 x 的大小关系，并通过比较的结果调整上下界的范围。由于我们所有的运算都是整数运算，不会存在误差

用 midx/mid 而不是 mid*midx 防止数值溢出

代码：

public class Solution {
 
      public  int MySqrt(int x)
        {
            if (x == 0) return 0;
            int left = 1, right = x, mid = (left+right)/2;
            while(left<right&&mid!=left)
            {
                if(mid== x/mid)
                {
                    return mid;
                }else if(mid < x / mid)
                {
                    left = mid;
                    mid = (left + right) / 2;
                }
                else
                {
                    right = mid;
                    mid = (left + right) / 2;
                }
            }
                return left;
        }
}

执行结果

通过
执行用时：44 ms，在所有 C# 提交中击败了57.74%的用户
内存消耗：14.7 MB，在所有 C# 提交中击败了1000.00%的用户

复杂度分析

时间复杂度：O( long x)
空间复杂度：O(1)

Java 方法一：二分法

思路解析

由于 x 平方根的整数部分 ans 是满足 k^2 ≤x 的最大 k 值，因此我们可以对 k 进行二分查找，从而得到答案。

二分查找的下界为 0，上界可以粗略地设定为 x。在二分查找的每一步中，我们只需要比较中间元素mid 的平方与 x 的大小关系，并通过比较的结果调整上下界的范围。

由于我们所有的运算都是整数运算，不会存在误差，因此在得到最终的答案 ans 后，也就不需要再去尝试ans+1 了。

代码：

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

执行结果

通过
执行用时：1 ms，在所有 Java  提交中击败了100.00%的用户
内存消耗：35.3 MB，在所有 Java 提交中击败了92.27%的用户

复杂度分析

时间复杂度：O( long x)
空间复杂度：O(1)

Java 方法二：牛顿迭代

思路解析

这个方法是力扣官方解答，放在这给大家看看即可，我并没有看得很明白。。。

class Solution {
    public int mySqrt(int x) {
        if (x == 0) {
            return 0;
        }

        double C = x, x0 = x;
        while (true) {
            double xi = 0.5 * (x0 + C / x0);
            if (Math.abs(x0 - xi) < 1e-7) {
                break;
            }
            x0 = xi;
        }
        return (int) x0;
    }
}

执行结果

通过
执行用时：1 ms，在所有 Java  提交中击败了100.00%的用户
内存消耗：35.5 MB，在所有 Java 提交中击败了57.42%的用户

复杂度分析

时间复杂度：O( long x)
空间复杂度：O(1)

总结

今天是力扣算法题打卡的第二十一天！
文章采用 C#和 Java 两种编程语言进行解题
一些方法也是参考力扣大神写的，也是边学习边分享，再次感谢算法大佬们
那今天的算法题分享到此结束啦，明天再见！

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2021/08/30 ，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

java

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

java

登录后参与评论

0 条评论

热度