LeetCode刷题实战69：x 的平方根
算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选 ！
今天和大家聊的问题叫做 x 的平方根，我们先来看题面：
https://leetcode-cn.com/problems/sqrtx/
Implement int sqrt(int x).
Compute and return the square root of x, where x is guaranteed to be a non-negative integer.
Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.
题意
实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
样例
示例 1:
输入: 4
输出: 2
示例 2:
输入: 8
输出: 2
说明: 8 的平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
解题
https://blog.csdn.net/qq_41231926/article/details/82861877
解法一：从1开始逐个查找
思路一是最先能想到的简单粗暴的解法。从数字1开始找，一旦找到平方值等于x的数字i，直接返回i。如果找到平方值大于x的数字i，需要返回i - 1。
需要注意的是，为了防止做乘法运算时越界，需要强转为long类型。
时间复杂度是O(sqrt(x))。空间复杂度是O(1)。
public class Solution {
public int mySqrt(int x) {
for (long i = 1; i <= x; i++) {
if(i * i > x) {
return (int)(i - 1);
}else if(i * i == x) {
return (int)i;
}
}
return 0;
}
}
解法二：二分查找法
解法一的时间复杂度太高，可以用二分法进行改进。
运算过程中涉及到乘法运算时同样需要强转为long类型防止越界。
时间复杂度是O(logx)。空间复杂度是O(1)。
public class Solution {
public int mySqrt(int x) {
int left = 0, right = x / 2 + 1;
while (left <= right) {
long mid = left + (right - left) / 2;
if (mid * mid == x) {
return (int) mid;
} else if (mid * mid < x) {
left = (int) (mid + 1);
} else {
right = (int) (mid - 1);
}
}
return right;
}
}
好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力。
上期推文：
下一篇： 剑指--旋转数组的最小数字