给定 正整数n，如果n是某个正整数的平方，即存在整数m，m*m=n，则输出m，否则输出0。

算法1：暴力枚举

时间复杂度：$O(\sqrt{n})$

C++ 代码

class Solution {
public:
int isPerfectSquare(int n) {
int m = sqrt(n);
if (m * m == n) {
return m;
} else {
return 0;
}
}
};

算法2：二分查找

时间复杂度：$O(\log n)$

C++ 代码

class Solution {
public:
int isPerfectSquare(int n) {
int left = 1, right = n;
while (left <= right) {
int mid = left + (right - left) / 2;
long long square = (long long)mid * mid;
if (square == n) {
return mid;
} else if (square < n) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return 0;
}
};

算法3：牛顿迭代法

时间复杂度：$O(\log n)$

C++ 代码

class Solution {
public:
int isPerfectSquare(int n) {
if (n < 2) {
return n;
}
double x = n;
while (fabs(x * x - n) > 1e-6) {
x = (x + n / x) / 2;
}
return (int)x;
}
};