【Day 29 】2021-06-07 - 69. x 的平方根
题目描述
69. x 的平方根
入选理由
暂无
题目地址
https://leetcode-cn.com/problems/sqrtx
前置知识
- 二分法
题目描述
实现 int sqrt(int x) 函数。 计算并返回 x 的平方根，其中 x 是非负整数。 由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。 示例 1: 输入: 4 输出: 2 示例 2: 输入: 8 输出: 2 说明: 8 的平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去
我的回答
解法一
时空复杂度
时间复杂度：O(logn)
空间复杂度: O(1)
var mySqrt = function (x) {
let left = 0;
let right = x;
while (left <= right) {
let mid = (left + right) >> 1;
if (Math.pow(mid, 2) > x) {
right = mid - 1;
} else if (Math.pow(mid, 2) < x) {
left = mid + 1;
} else {
return mid;
}
}
return right;
};