一:题目
解释:返回x的算数平方根,如果是小数,则舍去小数部分,返回整数即可!
二:算法
①:暴力
从1开始求平方,最后要么直接找到一个值的平方为x,要么发现x在两个相邻的数的平方之间
暴力的时间复杂度为O(N)
但是我们从暴力得知,最后返回的一定是left,因为双指针相遇返回left和right都可以,但是如果发现x是两个相邻的数的平方之间,则返回left,因为题目要求向下取整
②:二分
做过了上道题目,此题简直如鱼得水!
我们将数组划分为两个部分,左部分值的平方<=x,右部分值的平方>x,本质是因为数组有可能没有直接平方等于x的值,所以左部分是<=
其次我们的区间的范围直接从1~x开始即可,因为只要一个数是正整数,则其一定小于其的平方!
所以:
mid*mid <=x 则left=mid //落入左部分
mid*mid >x 则right=mid-1 //落入右部分
很显然,我们的求中点的式子必须为:mid = left + (right - left + 1) / 2!
因为,我们说过mid不能落在原地踏步的指针上,此题left=mid,所以不能落在left上,所以我们选择该式子,当只有两个元素的时候,mid会落在right指针上
其次循环的条件必定是left<right,避免双指针相遇再次进入循环,导致原地踏步死循环!
三:代码
class Solution {
public:int mySqrt(int x) {if (x < 1) return 0;int left = 1, right = x;while (left < right) {long long mid = left + (right - left + 1) / 2;//long long 防溢出if (mid * mid <= x) left = mid;else right = mid - 1;}return left;}
};
解释:
1:循环条件,left<right
2:求中点式子,mid = left + (right - left + 1) / 2;
3:返回的是left
4:x可能为0~1之间,所以一开始特判即可