当前位置:网站首页>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)
参考
边栏推荐
- NTT的Another Me技术助力创造歌舞伎演员中村狮童的数字孪生体,将在 “Cho Kabuki 2022 Powered by NTT”舞台剧中首次亮相
- 1061 True or False (15 points)
- Douyin API interface
- 6月各手机银行活跃用户较快增长,创半年新高
- 1002 Write the number (20 points)
- Edge provides label grouping functionality
- 1091 N-Defensive Number (15 points)
- 你是如何做好Unity项目性能优化的
- About # SQL problem: how to set the following data by commas into multiple lines, in the form of column display
- 接入网、承载网、核心网是什么,交换机路由器是什么、这个和网络的协议有什么关系呢?
猜你喜欢
Tidb二进制集群搭建
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
Serverless + domain name can also build a personal blog? Really, and soon
Item 2 - Annual Income Judgment
1101 B是A的多少倍 (15 分)
1061 判断题 (15 分)
1051 复数乘法 (15 分)
公牛10-11德里克·罗斯最强赛季记录
Test cases are hard?Just have a hand
Tf中的平方,多次方,开方计算
随机推荐
There may be fields that cannot be serialized in the abnormal object of cdc and sqlserver. Is there anyone who can understand it? Help me to answer
matrix multiplication in tf
【LeetCode每日一题】——844.比较含退格的字符串
Douyin API interface
Unity游戏排行榜的制作与优化
Service的两种状态形式
Strongly recommend an easy-to-use API interface
【Pytorch】nn.Linear,nn.Conv
伦敦银规则有哪些?
项目1-PM2.5预测
2022-08-10 Group 4 Self-cultivation class study notes (every day)
Tensorflow中使用tf.argmax返回张量沿指定维度最大值的索引
流式结构化数据计算语言的进化与新选择
1.1-Regression
易观分析联合中小银行联盟发布海南数字经济指数,敬请期待!
linux 安装mysql服务报错
【LeetCode】链表题解汇总
深度监督(中继监督)
年薪40W测试工程师成长之路,你在哪个阶段?
1036 Programming with Obama (15 points)