LeetCode69 Sqrt(x)

文章目录
  1. 1. 描述
  2. 2. 样例
  3. 3. 思路
  4. 4. 代码

描述

Implement int sqrt(int x).

Compute and return the square root of x.

样例

1
2
Input:
4
1
2
Output:
2

思路

实现开根函数,返回值向下取整。

一种方法是二分搜索答案,每次检查$mid^2$和$x$的关系来更新上下界。

另外,也可以使用牛顿迭代法。迭代公式:$f(x) = x^2 - n$,$x_{n+1}$ = $x_{n} - \frac{f(x_{n})}{f^{‘}(x_{n})}$ = $x_{n} - \frac{x_{n}^2-n}{2x_{n}}$ = $(x_n + \frac{n}{x_n}) / 2$

代码

二分:

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
int mySqrt(int x) {
long long l = 0, r = x, m;
while (l < r) {
m = l + (r - l + 1) / 2;
if (m * m <= x) l = m;
else r = m - 1;
}
return l;
}
};

牛顿迭代法:

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
int mySqrt(int x) {
double x0 = 0, x1 = 1;
while (fabs(x0 - x1) > 1e-6) {
x0 = x1;
x1 = (x0 + x / x0) / 2;
}
return int(x0);
}
};
分享到 评论