当前位置:网站首页>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)
参考
边栏推荐
猜你喜欢
1051 Multiplication of Complex Numbers (15 points)
matrix multiplication in tf
Use tf.argmax in Tensorflow to return the index of the maximum value of the tensor along the specified dimension
关于Excel实现分组求和最全文档
TF中的条件语句;where()
【软件测试】(北京)字节跳动科技有限公司二面笔试题
基于FPGA的FIR滤波器的实现(4)— 串行结构FIR滤波器的FPGA代码实现
1071 小赌怡情 (15 分)
1056 组合数的和 (15 分)
1091 N-自守数 (15 分)
随机推荐
6月各手机银行活跃用户较快增长,创半年新高
项目1-PM2.5预测
cdc连sqlserver异常对象可能有无法序列化的字段 有没有大佬看得懂的 帮忙解答一下
1091 N-Defensive Number (15 points)
2021-08-11 for循环结合多线程异步查询并收集结果
易观分析联合中小银行联盟发布海南数字经济指数,敬请期待!
Unity游戏排行榜的制作与优化
进制转换间的那点事
STM32CUBEIDE(11)----输出PWM及修改PWM频率与占空比
2022-08-09 Group 4 Self-cultivation class study notes (every day)
从苹果、SpaceX等高科技企业的产品发布会看企业产品战略和敏捷开发的关系
Unity底层是如何处理C#的
1002 写出这个数 (20 分)
我的创作纪念日丨感恩这365天来有你相伴,不忘初心,各自精彩
【latex异常和错误】Missing $ inserted.<inserted text>You can‘t use \spacefactor in math mode.输出文本要注意特殊字符的转义
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
1081 Check Password (15 points)
2022年中国软饮料市场洞察
【Pytorch】nn.Linear,nn.Conv
1071 小赌怡情 (15 分)