当前位置:网站首页>leetcode: 69. Square root of x
leetcode: 69. Square root of x
2022-08-11 07:53: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
解法
- 库函数:This kind of general problem solving is not allowed to use library functions
- 循环:从1Start training traversal,求n*n与x的关系
- 二分法:Accelerates traversal search by dichotomy
- 牛顿法:数学公式推导
代码实现
遍历
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) , But still faster than the dichotomy
- 空间复杂度: O ( 1 ) O(1) O(1)
参考
边栏推荐
- TF中的四则运算
- 数仓开发知识总结
- 2022-08-09 Group 4 Self-cultivation class study notes (every day)
- Do you know the basic process and use case design method of interface testing?
- The most complete documentation on Excel's implementation of grouped summation
- 2022-08-10 mysql/stonedb-慢SQL-Q16-耗时追踪
- 公牛10-11德里克·罗斯最强赛季记录
- 3.1-分类-概率生成模型
- 恒源云-Pycharm远程训练避坑指南
- 租房小程序
猜你喜欢
随机推荐
tf.cast(),reduce_min(),reduce_max()
1051 Multiplication of Complex Numbers (15 points)
Discourse's Close Topic and Reopen Topic
Redis source code: how to view the Redis source code, the order of viewing the Redis source code, the sequence of the source code from the external data structure of Redis to the internal data structu
语音信号处理:预处理【预加重、分帧、加窗】
2022-08-09 Group 4 Self-cultivation class study notes (every day)
The softmax function is used in TF;
Activity的四种启动模式
2.1 - Gradient Descent
1056 组合数的和 (15 分)
年薪40W测试工程师成长之路,你在哪个阶段?
2022年中国软饮料市场洞察
【Pytorch】nn.ReLU(inplace=True)
动态代理学习
【latex异常和错误】Missing $ inserted.<inserted text>You can‘t use \spacefactor in math mode.输出文本要注意特殊字符的转义
线程交替输出(你能想出几种方法)
1002 写出这个数 (20 分)
1076 Wifi密码 (15 分)
流式结构化数据计算语言的进化与新选择
Tidb二进制集群搭建