博客

1.暴力解法–袖珍计算器

class Solution {
public:
    int mySqrt(int x) {
        
       int y=exp(0.5*log(x));
       if((y+1)*(y+1)>=x)
       return (y+1);
       else return y;
    }
       
};

复杂度分析

时间复杂度：O(1)，由于内置的 exp 函数与 log 函数一般都很快，我们在这里将其复杂度视为 O(1)

空间复杂度：O(1)。

2.二分查找

#include<iostream>
using namespace std;
class Solution {
public:
	int mySqrt(int x) {
		int l = 0, r = x,index=0;
		for (; l < x;) {
			int mid = l + (r - 1) / 2;
			if (mid * mid <= x) {
				index = mid;
				l = mid + 1;
			}
			else {
				index = mid;
				r = mid - 1;
			}
		}
			return index;
		
	}

};
int main()
{
	Solution A;
	A.mySqrt(25);
}

复杂度分析

• 时间复杂度：O(logx)，即为二分查找需要的次数。

• 空间复杂度：O(1)。