题目描述:
实现 int sqrt(int x) 函数。
计算并返回 x 的平方根,其中 x 是非负整数。
由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。
示例 1:
输入: 4
输出: 2
示例 2:
输入: 8
输出: 2
说明: 8 的平方根是 2.82842...,由于返回类型是整数,小数部分将被舍去。
解法一:暴力法
思路:暴力法的思路很简单,就是从1开始遍历到x。
(1)如果index的平方小于等于x,则继续遍历。
(2)如果index平方大于x,则直接返回index-1。
注意:关于index的类型,如果使用int,则在判断条件处使用index <= x/index来作为条件,防止溢出。如果index类型是long,则判断条件处可使用index*index<=x。
代码:
class Solution {
public int mySqrt(int x) {
int index =1;
while(index <= x/index){
index ++;
}
return index-1;
}
}
解法二:二分查找。
思路:
对x进行二分查找,在每次进行二分查找的过程中,只需要比较中间元素的平方值和x的大小即可。如果mid的平方比x大,则让right = mid-1;如果mid的平方比x小,则left = mid + 1。
注意:为了防止溢出,在判断的时候采用mid == x/mid来判断是否相等。
代码:
class Solution {
public int mySqrt(int x) {
int left = 1, right = x;
int mid = 0;
while(left <= right){
mid = left + (right - left) / 2;
if(mid < x/mid){
left = mid + 1;
}else if(mid == x/mid){//避免乘法溢出
return mid;
}else{
right = mid -1;
}
}
return right;
}
}
解法三:牛顿迭代法。
思路:
如果n^2=x,则可以变为n=x/n。如果n的平方就是x,那么n和x/n的值是相等。以12为例:12=2 * 6 ,如果n=2是x的平方根,那么x/n就应该等于n,然而并不是,那么此时就可以取n和x/n的平均值,也就是4,这样就可以更加逼近12。因为2的平方是4,6的平放方是36,而4的平方则是16,更加接近12。通过这样不断地迭代,就可以得到最终的结果。因此,总结出公式:假设变量为val,则每次迭代 val = ( val + x / val) /2。
代码:
class Solution {
public int mySqrt(int x) {
long right = x;
while(right * right > x){
right = (right + x/right)/2;
}
return (int)right;
}
}
还有一种办法就是直接使用Java的库:Math.sqrt()。