当前位置:网站首页>leetcode:69. x 的平方根
leetcode:69. x 的平方根
2022-08-11 07:00:00 【uncle_ll】
69. x 的平方根
来源:力扣(LeetCode)
链接: https://leetcode.cn/problems/sqrtx/
给你一个非负整数 x ,计算并返回 x 的 算术平方根 。
由于返回类型是整数,结果只保留 整数部分 ,小数部分将被 舍去 。
注意:不允许使用任何内置指数函数和算符,例如 pow(x, 0.5) 或者 x ** 0.5 。
示例 1:
输入:x = 4
输出:2
示例 2:
输入:x = 8
输出:2
解释:8 的算术平方根是 2.82842..., 由于返回类型是整数,小数部分将被舍去。
提示:
- 0 <= x <= 2 31 − 1 2^{31} - 1 231−1
解法
- 库函数:这种一般解题的话不让用库函数
- 循环:从1开始训练遍历,求n*n与x的关系
- 二分法:通过二分法加速遍历寻找
- 牛顿法:数学公式推导
代码实现
遍历
python实现
class Solution:
def mySqrt(self, x: int) -> int:
if x == 0:
return 0
n = 1
while n * n <= x:
n += 1
return n-1
c++实现
class Solution {
public:
int mySqrt(int x) {
if ( x == 0 || x == 1)
return x;
long int n = 1;
while (n * n <= x) {
n++;
}
return n-1;
}
};
复杂度分析
- 时间复杂度: O ( N ) O(N) O(N)
- 空间复杂度: O ( 1 ) O(1) O(1)
二分法
python实现
class Solution:
def mySqrt(self, x: int) -> int:
if x == 0:
return 0
right = x
left = 0
while left <= right:
mid = left + (right-left) // 2
if mid * mid < x:
left = mid + 1
elif mid * mid == x:
return mid
elif mid * mid > x:
right = mid - 1
return min(left, right)
c++实现
class Solution {
public:
int mySqrt(int x) {
if (x == 0 || x == 1)
return x;
long int left = 0;
long int right = x;
while (left <= right) {
long int mid = left + (right-left) / 2;
if (mid * mid == x)
return mid;
else if (mid * mid < x) {
left = mid + 1;
}
else if (mid * mid > x) {
right = mid - 1;
}
}
return min(left, right);
}
};
复杂度分析
- 时间复杂度: O ( l o g N ) O(logN) O(logN)
- 空间复杂度: O ( 1 ) O(1) O(1)
牛顿法
- python实现
class Solution:
def mySqrt(self, x: int) -> int:
if x == 0:
return 0
C, x0 = float(x), float(x)
while True:
xi = 0.5 * (x0 + C / x0)
if abs(x0 - xi) < 1e-7:
break
x0 = xi
return int(x0)
- c++实现
class Solution {
public:
int mySqrt(int x) {
if (x == 0) {
return 0;
}
double C = x, x0 = x;
while (true) {
double xi = 0.5 * (x0 + C / x0);
if (fabs(x0 - xi) < 1e-7) {
break;
}
x0 = xi;
}
return int(x0);
}
};
复杂度分析
- 时间复杂度: O ( l o g N ) O(logN) O(logN) , 但还是比二分法要快
- 空间复杂度: O ( 1 ) O(1) O(1)
参考
边栏推荐
- 接入网、承载网、核心网是什么,交换机路由器是什么、这个和网络的协议有什么关系呢?
- 1081 Check Password (15 points)
- [Recommender System]: Overview of Collaborative Filtering and Content-Based Filtering
- prometheus学习4Grafana监控mysql&blackbox了解
- 1051 复数乘法 (15 分)
- 1046 punches (15 points)
- 1061 True or False (15 points)
- 1106 2019 Sequence (15 points)
- 1056 组合数的和 (15 分)
- 1096 big beautiful numbers (15 points)
猜你喜欢
随机推荐
matplotlib
1056 Sum of Combinations (15 points)
【LeetCode每日一题】——682.棒球比赛
break pad源码编译--参考大佬博客的总结
Pinduoduo API interface
求职简历这样写,轻松搞定面试官
1071 小赌怡情 (15 分)
【LeetCode每日一题】——844.比较含退格的字符串
golang fork 进程的三种方式
TF通过feature与label生成(特征,标签)集合,tf.data.Dataset.from_tensor_slices
2021-08-11 for循环结合多线程异步查询并收集结果
恒源云-Pycharm远程训练避坑指南
TF中的四则运算
从苹果、SpaceX等高科技企业的产品发布会看企业产品战略和敏捷开发的关系
1003 I want to pass (20 points)
My creative anniversary丨Thank you for being with you for these 365 days, not forgetting the original intention, and each is wonderful
C语言每日一练——Day02:求最小公倍数(3种方法)
公牛10-11德里克·罗斯最强赛季记录
年薪40W测试工程师成长之路,你在哪个阶段?
maxwell concept