likes
comments
collection
share

LeetCode第69题x 的平方根

作者站长头像
站长
· 阅读数 15

继续打卡算法题,今天学习的是LeetCode第69题x的平方根 ,这道题目是道简单题。算法题的一些解题思路和技巧真的非常巧妙,每天看一看算法题和解题思路,我相信对我们的编码思维和编码能力有一些提升。

LeetCode第69题x 的平方根

分析一波题目

本题要求算术平方根,如果我们使用暴力办法,可以从1到2/x,不断的求平方根,这样时间复杂度是2/x。

我们可以使用二分的思想,不断的找一个这样的数,满足k^2≤x, 并且k取最大值。这样都不需要查找x/2次了,时间复杂度降低为O(logx)

本题解题思路

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、二分思想是比较常见的解题思路,这个简单题目可以了解到二分思想的作用

转载自:https://juejin.cn/post/7292692843415404553
评论
请登录