嘉兴北京网站建设,seo网站优化经理,怎么做信息流广告代理商,网站推广公司简介给你一个非负整数 x #xff0c;计算并返回 x 的 算术平方根 。
由于返回类型是整数#xff0c;结果只保留 整数部分 #xff0c;小数部分将被 舍去 。
注意#xff1a;不允许使用任何内置指数函数和算符#xff0c;例如 pow(x, 0.5) 或者 x ** 0.5 。 示例 1#xff1…给你一个非负整数 x 计算并返回 x 的 算术平方根 。
由于返回类型是整数结果只保留 整数部分 小数部分将被 舍去 。
注意不允许使用任何内置指数函数和算符例如 pow(x, 0.5) 或者 x ** 0.5 。 示例 1
输入x 4 输出2 示例 2
输入x 8 输出2 解释8 的算术平方根是 2.82842..., 由于返回类型是整数小数部分将被舍去。
提示
0 x 231 - 1
来源力扣LeetCode 链接https://leetcode.cn/problems/sqrtx 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 思路
答案一定在区间0-x中那么可以利用二分法来查找答案sqrt当sqrtx/sqrt的时候sqrt即为答案。
首先定义mid l h-l/2如果sqrtx/mid说明sqrt大于结果结果应在[mid1~h]的区间内反之在[l~mid-1]区间内。
对于 x 8它的开方是 2.82842...最后应该返回 2 而不是 3。在循环条件为 l h 并且循环退出时h 总是比 l 小 1也就是说 h 2l 3因此最后的返回值应该为 h 而不是 l。
代码如下
class Solution {public int mySqrt(int x) {int l 1, h x;while (l h) {int mid l (h - l) / 2;int sqrt x / mid;if (sqrt mid) {return sqrt;} else if (sqrt mid) {h mid - 1;} else {l mid 1;}}return h;}
}
