当前位置:网站首页>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)
参考
边栏推荐
猜你喜欢
随机推荐
少年成就黑客,需要这些技能
1081 检查密码 (15 分)
tf中矩阵乘法
分布式锁-Redission - 缓存一致性解决
1071 小赌怡情 (15 分)
1.1-Regression
Discourse's Close Topic and Reopen Topic
TF generates (feature, label) set through feature and label, tf.data.Dataset.from_tensor_slices
【latex异常和错误】Missing $ inserted.<inserted text>You can‘t use \spacefactor in math mode.输出文本要注意特殊字符的转义
详述 MIMIC护理人员信息表(十五)
1036 跟奥巴马一起编程 (15 分)
Do you know the basic process and use case design method of interface testing?
tf.reduce_mean()与tf.reduce_sum()
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?
Four states of Activity
DDR4内存条电路设计
Use tf.argmax in Tensorflow to return the index of the maximum value of the tensor along the specified dimension
年薪40W测试工程师成长之路,你在哪个阶段?
tf.reduce_mean() and tf.reduce_sum()
从苹果、SpaceX等高科技企业的产品发布会看企业产品战略和敏捷开发的关系