问题
1 | Implement int sqrt(int x). |
翻译:
实现int sqrt(int x)。
计算并返回x的平方根，其中x保证是一个非负整数。
由于返回类型是整数，因此将截断小数，只返回结果的整数部分。
示例1:
输入:4
输出:2
示例2:
输入:8
输出:2
说明:8的平方根是2.82842…,自
小数部分被截断，返回2。
解题思路
本题是找一个数是当前数的平方根，如果是小数，则返回舍弃小数的值。我们可以用遍历的方式，来判断是不是，当时这边需要考虑一下越界的问题，其实也可以不关注，毕竟可以得出越界的上限的平方根是多少，就可以避免这个问题。除了遍历，我们也可以用java自带的Math类来解决，是最简单的。除此之外，本题是找值，而且是在特定范围内找一个值，就可以想到是否可以用二分法来简短查询时间。
解题方法
按照我们的思路来编辑，代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14if (x <= 0) {
return 0;
}
for (int i =x/2+1; i>=0; i=i/2) {
long result = 1L*i * i;
if (result == x) {
return i;
}
if (result > x) {
return i - 1;
}
}
return 0;时间复杂度: 该方案用了循环m所以f(n)=(n/2)=n;所以O(f(n))=O(n/2),即T(n)=O(n)
空间复杂度: 该方案使用了没有使用额外空间，所以空间复杂度是O(n)=O(1);
使用二分法，代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15if (x <= 0) {
return 0;
}
int start = 0;
int end = x;
while (start <= end) {
int index = (start + end) / 2;
long sum = 1L * index * index;
if (sum > x) {
end = index - 1;
} else {
start = index + 1;
}
}
return end;时间复杂度: 该方案用了循环m所以f(n)=(logn)=n;所以O(f(n))=O(logn),即T(n)=O(logn)
空间复杂度: 该方案使用了没有使用额外空间，所以空间复杂度是O(n)=O(1);
借用Math类，代码如下
1
2
3
4
5if (x <= 0) {
return 0;
}
return (int)Math.sqrt(x);时间复杂度: 该方案用了循环m所以f(n)=(1)=n;所以O(f(n))=O(1),即T(n)=O(1)
空间复杂度: 该方案使用了没有使用额外空间，所以空间复杂度是O(n)=O(1);
总结
本题的大致解法如上所诉, 在特地范围内，而且还是有序的，我们自然可以想到二分法来简化遍历，由于这题是需要最近的最小值，所以当end–后，大的值就变成来最小值，刚刚好满足。