题意概述

• 对于给定的int型整数
• 计算它的下取整平方根

方法一：数学

思路与具体做法

• 用对数恒等式写成下面这个形式
• $x=x^{1/2}=(e^x{)}^{1/2}=e^{\frac{1}{2}\left(x\right)}\backslash mysqrt\{x\}\; =x^\{1/2\}\; =\; (e^\{\backslash ln\_\{\}\{x\}\; \}\; )^\{1/2\}=\; e^\{\backslash frac\{1\}\{2\}\; \backslash ln\_\{\}(\{x\})\; \}$x​=x1/2=(eln​x)1/2=e21​ln​(x)
• 注意因为浮点数的精确值不好表示，可能存在误差，所以算出来的ans要和ans+1进行比较

class Solution {
public:
    int mysqrt(int x) {
        int ans=exp(log(x)*0.5);//写成对数恒等式
		ans=(ans+1)*(ans+1)<=x?ans++:ans;//是否可以更加逼近
		return ans;
    }
};

时间复杂度和空间复杂度分析

• 时间复杂度：$O\left(1\right)O(1)$O(1)，内置log函数
• 空间复杂度：$O\left(1\right)O(1)$O(1)，仅设立了几个整形变量

方法二：二分查找

思路与具体做法

• 使用二分查找，在[0,x]里找某个数的平方趋于x的
• 二分查找下界l设为0，上界r设为x
• 每次比较中间元素mid的平方与x的大小
• 下取整，即mid的平方趋于但小于x，将ans=mid放在mid*mid<=x的情况里

class Solution {
public:
    int mysqrt(int x) {
        int l=0,r=x,ans;
        while(l<=r){
        	int mid=l+(r-l)/2;//防止溢出
        	if((long long)mid*mid<=x)ans=mid,l=mid+1;//因为是下取整这里将ans=mid放在<=的情况里 
			else r=mid-1; 
		}
		return ans;
    }
};

时间复杂度和空间复杂度分析

• 时间复杂度：$O\left(2_{}x\right)O(\backslash log\_\{2\}\{x\}\; )$O(log2​x)，即为二分查找需要的次数
• 空间复杂度：$O\left(1\right)O(1)$O(1)，仅设立了几个整形变量