leetcode 69 x 的平方根 二分查找 牛顿迭代法

缘起

日常浪费生命~ leetcode 69 x 的平方根

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
实现 int sqrt(int x) 函数。

计算并返回 x 的平方根，其中 x 是非负整数。

由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

示例 1:

输入: 4
输出: 2
示例 2:

输入: 8
输出: 2
说明: 8 的平方根是 2.82842..., 
由于返回类型是整数，小数部分将被舍去。

本题如果仅仅是求整数的话, 就太简单了——不涉及浮点数的操作. 二分查找即可（这都是标准的板子了）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
	int mySqrt(int x) {
		long long lo = 0,hi = x, mid,ans=-1;
		while(lo<=hi)
		{
			mid = (lo+hi)>>1;
			if (mid*mid<=x) // 这里使用long long是为了防止这里越界int
			{
				ans = mid;
				lo = mid+1;
			}
			else
			{
				hi = mid-1;
			}
		}
		return ans;
	}
};

ac情况

1
2
3
4
5
6
7
8
9
10
11
12
13
执行结果：
通过
显示详情
执行用时 :
8 ms
, 在所有 C++ 提交中击败了
60.21%
的用户
内存消耗 :
8.1 MB
, 在所有 C++ 提交中击败了
90.60%
的用户

当然，如果不想使用long long的话，可以引入 math.h 然后

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
	int mySqrt(int x) {
		int lo = 0,hi = x, mid,ans=-1;
		while(lo<=hi)
		{
			mid = (lo+hi)>>1;
			if (mid<=floor(sqrt(1.0*x)))
			{
				ans = mid;
				lo = mid+1;
			}
			else
			{
				hi = mid-1;
			}
		}
		return ans;
	}
};

ac情况

1
2
3
4
5
6
7
8
9
10
11
12
13
执行结果：
通过
显示详情
执行用时 :
4 ms
, 在所有 C++ 提交中击败了
90.09%
的用户
内存消耗 :
8.3 MB
, 在所有 C++ 提交中击败了
74.36%
的用户

当然，如果这样的话，本题意义不大. 我们可以精确的求出平方根，然后截取其整数部分即可. 而精确的求平方根（我们精确到第六位）有二分查找或者牛顿迭代

二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
	int mySqrt(int x) {
		double lo = 0,hi = x, mid,ans=lo, eps=1e-8;
		while(lo+eps<=hi)
		{
			mid = (lo+hi)/2;
			if (mid*mid<x+eps) // 如果mid*mid<=x
			{
				ans = mid;
				lo = mid;
			}
			else
			{
				hi = mid;
			}
		}
		return ans+eps; // 防止丢失精度,例如1返回的ans是0.9999....
	}
};

ac情况

1
2
3
4
5
6
7
8
9
10
11
12
13
执行结果：
通过
显示详情
执行用时 :
8 ms
, 在所有 C++ 提交中击败了
60.21%
的用户
内存消耗 :
8.2 MB
, 在所有 C++ 提交中击败了
77.26%
的用户

牛顿迭代

牛顿迭代的原理如下

求f(x)=0的根. 如果x0不是f(x)=0的根的话，则做(x0,f(x0))点出的切线, 然后求出该切线与x轴的交点. 则该交点坐标将快速收敛到f(x)=0的一个根. 收敛速度是二阶无穷小（泰勒展开可以证明）. 速度很快~

对于求平方根，即求 x^2-n=0的根. 则牛顿迭代的公式就显然了

1
2
3
假设x0不是n的平方根, 则
xn = x_{n-1}/2+n/2/x_{n-1}
不断迭代即可

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
	int mySqrt(int x) {
		if (!x)
		{
			return 0;
		}
		double a = x, b=-1, eps = 1e-8;
		while(1)
		{
			b = a/2+x/a/2;
			if (b+eps>a)
			{
				return b+eps; // 防止丢失精度
			}
			a = b;
		}
	}
};

ac情况

1
2
3
4
5
6
7
8
9
10
11
12
13
执行结果：
通过
显示详情
执行用时 :
8 ms
, 在所有 C++ 提交中击败了
60.21%
的用户
内存消耗 :
8.2 MB
, 在所有 C++ 提交中击败了
75.47%
的用户