「优选算法刷题」:x的平方根
一、题目
给你一个非负整数 x
,计算并返回 x
的 算术平方根 。
由于返回类型是整数,结果只保留 整数部分 ,小数部分将被 舍去 。
注意:不允许使用任何内置指数函数和算符,例如 pow(x, 0.5)
或者 x ** 0.5
。
示例 1:
输入:x = 4 输出:2
示例 2:
输入:x = 8 输出:2 解释:8 的算术平方根是 2.82842..., 由于返回类型是整数,小数部分将被舍去。
二、思路解析
这道题可以用二分查找来解答,主要是因为算术平方根的性质。
一个非负整数 x,它的算术平方根一定在区间 [0, x] 内,而且随着平方根的增大,其平方值也会逐渐增大,因此平方根与 x 的大小关系是单调的。
还记得我之前说的吗,看到单调性和二段性就要想到二分查找,利用它来缩小平方根的搜索范围。
具体就是,我们在区间 [0, x] 中查找一个数 mid,如果 mid 的平方小于等于 x,那么我们就在区间 [mid+1, x] 中继续查找;否则,我们就在区间 [0, mid-1] 中继续查找。直到区间缩小到一个数,也就是平方根的整数部分。
具体实现请看下面代码👇
三、完整代码
class Solution {
public int mySqrt(int x) {
if(x < 1){
return 0;
}
long left = 1;
long right = x;
while(left < right){
long mid = left + (right - left + 1) / 2;
if(mid * mid <= x){
left = mid;
}else{
right = mid - 1;
}
}
return (int)left;
}
}
以上就是本篇博客的全部内容啦,如有不足之处,还请各位指出,期待能和各位一起进步!
原文地址:https://blog.csdn.net/C_Small_Cai/article/details/136149112
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!