当前位置:网站首页>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)
参考
边栏推荐
- 1096 大美数 (15 分)
- 1061 判断题 (15 分)
- C语言每日一练——Day02:求最小公倍数(3种方法)
- 关于#sql#的问题:怎么将下面的数据按逗号分隔成多行,以列的形式展示出来
- Find the latest staff salary and the last staff salary changes
- Four startup modes of Activity
- 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-10 mysql/stonedb-slow SQL-Q16-time-consuming tracking
- Serverless + domain name can also build a personal blog? Really, and soon
- TF中的One-hot
猜你喜欢
随机推荐
关于#sql#的问题:怎么将下面的数据按逗号分隔成多行,以列的形式展示出来
redis操作
DDR4内存条电路设计
少年成就黑客,需要这些技能
Four operations in TF
Production and optimization of Unity game leaderboards
1046 划拳 (15 分)
详述 MIMIC护理人员信息表(十五)
Redis source code-String: Redis String command, Redis String storage principle, three encoding types of Redis string, Redis String SDS source code analysis, Redis String application scenarios
接入网、承载网、核心网是什么,交换机路由器是什么、这个和网络的协议有什么关系呢?
1076 Wifi密码 (15 分)
Find the latest staff salary and the last staff salary changes
What are the things that should be planned from the beginning when developing a project with Unity?How to avoid a huge pit in the later stage?
2022-08-09 Group 4 Self-cultivation class study notes (every day)
2.1 - Gradient Descent
4.1-支持向量机
1.2-误差来源
1076 Wifi Password (15 points)
【软件测试】(北京)字节跳动科技有限公司终面HR面试题
Pico neo3 Unity打包设置