x-的平方根

Tips

题目类型: Math

题目

计算一个数字的平方根, 结果向下取整. 如 24 的平方根返回 4.

提示:

• 0 <= x <= 2³¹ - 1

示例

输入: 24

输出: 4

题解

因为平方根一定小于等于 x 的一半, 为减少遍历次数, 可先将 x 减半. 对于平方根此定律: i * i <= x < (i + 1) * (i + 1), 直接套用即可.

JavaScript

/**
 * @param {number} x
 * @return {number}
 */
var mySqrt = function (x) {
  if (x < 2) return x

  const half = (x / 2) | 0
  for (let i = 1; i <= half; i++) {
    if (i * i <= x && (i + 1) * (i + 1) > x) return i
  }
}

Rust

Rust 版本需要注意的是 (i + 1) * (i + 1) 可能会突破 i32 的最大值, 因此你需要在 i64 的基础上完成这道题.

#[allow(unused)]
pub fn my_sqrt(x: i32) -> i32 {
    if x < 2 {
        return x;
    }

    let half = (x / 2) as i64;
    for i in 1..=half {
        if i * i <= x as i64 && (i + 1) * (i + 1) > x as i64 {
            return i as i32;
        }
    }

   x
}