69.x的平方根.md

69. x 的平方根

url

题目

实现 int sqrt(int x) 函数。

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

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

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

方法

二分法的思想

• 在(1, x)的区间中找一个res可以满足题意。
• 左点为1，右点为x，中点m为l + (r - l) / 2
• 乘法可能会溢出，因此改为m和x / m的判断
• 如果m >= x / m，则说明res在左边，那么另r = m，限定r的范围
• 如果m < x / m，则说明res在右边，那么另l = m + 1
• 最后判断m和x / m的值，若大于后者，则res为l - 1, 否则为l

code

js

let mySqrt = x => {
    let l = 1, r = x;
    while (l < r) {
        let m = Math.floor(l + (r - l) / 2);
        if (m >= Math.floor(x / m)) {
            r = m;
        } else {
            l = m + 1;
        }
    }
    return l > Math.floor(x / l) ? (l - 1) : l;
}

console.log(mySqrt(4));
console.log(mySqrt(8));

go

func mySqrt(x int) int {
	l, r := 1, x
	for l < r {
		m := l + (r - l) / 2
		if m >= x/m {
			r = m
		} else {
			l = m + 1
		}
	}
	if l > x / l {
		return l - 1
	} else {
		return l
	}
}

java

class Solution {
    public int mySqrt(int x) {
        int l = 1, r = x;
        while(l<r){
            int mid = l + (r - l) / 2;
            if(mid >= x / mid){     // 乘法可能会溢出， 改为除法
                r = mid;
            }else{
                l = mid+1;
            }
        }
        return l>x/l ? (l-1):l;  // 乘法可能会溢出， 改为除法
    }
}