367 Valid Perfect Square 有效的完全平方數(shù)
Description:
Given a positive integer num, write a function which returns True if num is a perfect square else False.
Note: Do not use any built-in library function such as sqrt.
Example :
Example 1:
Input: 16
Output: true
Example 2:
Input: 14
Output: false
題目描述:
給定一個(gè)正整數(shù) num，編寫(xiě)一個(gè)函數(shù)谈飒，如果 num 是一個(gè)完全平方數(shù)萨螺，則返回 True骑冗，否則返回 False玫氢。
說(shuō)明: 不要使用任何內(nèi)置的庫(kù)函數(shù)厂榛，如 sqrt。
示例 :
示例 1：
輸入：16
輸出：True
示例 2：
輸入：14
輸出：False
思路:
- 利用正奇數(shù)之和等于平方數(shù) 1 + 3 + ... + (2n - 1) = n ^ 2
- 二分查找
最大的平方數(shù)為 46340 ^ 2 < 2 ^ 31 - 1
時(shí)間復(fù)雜度O(logn), 空間復(fù)雜度O(1)
代碼:
C++:
class Solution
{
public:
bool isPerfectSquare(int num)
{
int temp = 1;
while (num > 0)
{
num -= temp;
temp += 2;
}
return num == 0;
}
};
Java:
class Solution {
public boolean isPerfectSquare(int num) {
int low = 0;
int high = num > 46340 ? 46340 : num;
while (low <= high) {
int mid = (low + high) / 2;
if (num == mid * mid) return true;
else if (num > mid * mid) low = mid + 1;
else high = mid - 1;
}
return false;
}
}
Python:
class Solution:
def isPerfectSquare(self, num: int) -> bool:
return (num in {i ** 2 for i in range(46341)})
