题目链接
题目描述：
给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。
进阶：不要 使用任何内置的库函数，如 sqrt 。
示例 1：
输入：num = 16 输出：true示例 2：
输入：num = 14 输出：false
方法一：库函数（C++代码）
class Solution {
public:
bool isPerfectSquare(int num) { //方法一：使用内置库函数
int x = (int) sqrt(num);
return pow(x, 2) == num;
}
};
代码中使用的 pow 函数的时空复杂度与 CPU 支持的指令集相关，这里不深入分析。
方法二：数学（C++代码）
分析：
1；
4=1+3；
9=1+3+5；
16=1+3+5+7；
25=1+3+5+7+9……
以此类推，模仿它可以使用一个while循环，不断减去一个从1开始不断增大的奇数，若最终减成了0，说明是完全平方数，否则，不是。
class Solution {
public:
// bool isPerfectSquare(int num) { //方法一：使用内置库函数
// int x = (int)sqrt(num);
// return pow(x, 2) == num;
// }
bool isPerfectSquare(int num) { //方法二：数学规律
int i = 1;
while(num > 0){
num -= i;
i += 2;
}
return num == 0;
}
};
- 时间复杂度：
- 空间复杂度：O(1)
方法三：暴力破解（C++代码）
class Solution {
public:
// bool isPerfectSquare(int num) { //方法一：使用内置库函数
// int x = (int)sqrt(num);
// return pow(x, 2) == num;
// }
// bool isPerfectSquare(int num) { //方法二：数学规律
// int i = 1;
// while(num > 0){
// num -= i;
// i += 2;
// }
// return num == 0;
// }
bool isPerfectSquare(int num) { //方法三：暴力破解
long x = 1, square = 1;
while(square <= num){
if(square == num){
return true;
}
x++;
square = x * x;
}
return false;
}
};
- 时间复杂度：
- 空间复杂度：O(1)
方法四：二分查找（C++代码）
class Solution {
public:
// bool isPerfectSquare(int num) { //方法一：使用内置库函数
// int x = (int) sqrt(num);
// return pow(x, 2) == num;
// }
// bool isPerfectSquare(int num) { //方法二：数学规律
// int i = 1;
// while(num > 0){
// num -= i;
// i += 2;
// }
// return num == 0;
// }
// bool isPerfectSquare(int num) { //方法三：暴力破解
// long x = 1, square = 1;
// while(square <= num){
// if(square == num){
// return true;
// }
// x++;
// square = x * x;
// }
// return false;
// }
bool isPerfectSquare(int num) { //方法四：二分查找
int left = 0, right = num;
while(left <= right){
int mid = left + (right - left) / 2;
long square = (long) mid * mid;
if(square < num){
left = mid + 1;
}else if(square > num){
right = mid - 1;
}else{
return true;
}
}
return false;
}
};
时间复杂度：O(logn)，其中 n 为正整数 num 的最大值。
空间复杂度：O(1)。
