367.Valid Perfect Square
Given a positive integer num, return true if num is a perfect square or false otherwise.
A perfect square is an integer that is the square of an integer. In other words, it is the product of some integer with itself.
You must not use any built-in library function, such as sqrt.
Example 1:
1
2
3
| Input: num = 16
Output: true
Explanation: We return true because 4 * 4 = 16 and 4 is an integer.
|
Example 2:
1
2
3
| Input: num = 14
Output: false
Explanation: We return false because 3.742 * 3.742 = 14 and 3.742 is not an integer.
|
暴力法：
时间复杂度：O(√n)
空间复杂度：O(1)
1
2
3
4
5
6
7
8
9
10
11
| class Solution {
public:
bool isPerfectSquare(int num) {
long n = 1;
while(n*n<=num) {
if(n*n == num)return true;
n++;
}
return false;
}
};
|
内置函数法：
1
2
3
4
5
6
7
| class Solution {
public:
bool isPerfectSquare(int num) {
int x = (int) sqrt(num);
return x * x == num;
}
};
|
二分法：
时间复杂度：O(logn)
空间复杂度：O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public:
bool isPerfectSquare(int num) {
int left = 0, right = num;
while (left <= right) {
int mid = (right - left) / 2 + left;
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)
空间复杂度：O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public:
bool isPerfectSquare(int num) {
double x0 = num;
while (true) {
double x1 = (x0 + num / x0) / 2;
if (x0 - x1 < 1e-6) {
break;
}
x0 = x1;
}
int x = (int) x0;
return x * x == num;
}
};
|