README_CN.md

69. x 的平方根

实现 int sqrt(int x) 函数。

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

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

示例 1:

输入: 4
输出: 2

示例 2:

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

题解 (Rust)

1. 暴力法

impl Solution {
    pub fn my_sqrt(x: i32) -> i32 {
        let mut n = 1;
        while n <= x / n {
            n += 1;
        }
        n - 1
    }
}

2. 二分查找

impl Solution {
    pub fn my_sqrt(x: i32) -> i32 {
        if x == 0 || x == 1 {
            return x;
        }
        let mut left = 0;
        let mut right = x;
        let mut mid = (left + right) / 2;
        loop {
            if mid <= x / mid && (mid + 1) > x / (mid + 1) {
                return mid;
            } else if mid > x / mid {
                right = mid;
            } else if mid < x / mid {
                left = mid;
            }
            mid = (left + right) / 2;
        }
    }
}

3. (n + 1)² = n² + 2n + 1

impl Solution {
    pub fn my_sqrt(x: i32) -> i32 {
        let mut n = 0;
        let mut x = x - 1;
        while x >= 0 {
            n += 1;
            x -= 2 * n + 1;
        }
        n
    }
}

4. 牛顿法

impl Solution {
    pub fn my_sqrt(x: i32) -> i32 {
        if x == 0 {
            return 0;
        }
        let x = x as usize;
        let mut n = x;
        while n > x / n {
            n = (n + x / n) / 2;
        }
        n as i32
    }
}