367. 有效的完全平方数
367. 有效的完全平方数
题目
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:
Input: num = 16
Output: true
Explanation: We return true because 4 * 4 = 16 and 4 is an integer.
Example 2:
Input: num = 14
Output: false
Explanation: We return false because 3.742 * 3.742 = 14 and 3.742 is not an integer.
Constraints:
1 <= num <= 231 - 1
题目大意
给你一个正整数 num
。如果 num
是一个完全平方数,则返回 true
,否则返回 false
。
完全平方数 是一个可以写成某个整数的平方的整数。换句话说,它可以写成某个整数和自身的乘积。
不能使用任何内置的库函数,如 sqrt
。
示例 1:
输入: num = 16
输出: true
解释: 返回 true ,因为 4 * 4 = 16 且 4 是一个整数。
示例 2:
输入: num = 14
输出: false
解释: 返回 false ,因为 3.742 * 3.742 = 14 但 3.742 不是一个整数。
提示:
1 <= num <= 231 - 1
解题思路
我们可以利用 二分查找 来高效判断 num
是否为完全平方数。
如果使用暴力法,从 1
到 num
遍历所有可能的整数,并判断其平方是否等于 num
,这种方法的时间复杂度为 O(sqrt(num))
,对于较大的 num
效率较低。
使用二分查找算法,可以在对数时间内找到 num
是否为完全平方数。假设 x
是 num
的平方根,我们可以限制 x
的取值范围在 [1, num]
。通过二分查找,逐步逼近 x
,检查中间值 mid
的平方是否等于 num
,并根据结果缩小搜索范围。
初始化
left = 1
和right = num
,定义搜索范围。计算中间值
mid = Math.floor((left + right) / 2)
。比较
mid * mid
和num
:- 如果
mid * mid == num
,返回true
。 - 如果
mid * mid > num
,说明平方根在左半部分,调整右边界:right = mid - 1
。 - 如果
mid * mid < num
,说明平方根在右半部分,调整左边界:left = mid + 1
。
- 如果
如果搜索完成后未找到满足条件的整数,返回
false
。
复杂度分析
- 时间复杂度:
O(log n)
,二分查找每次搜索将范围缩小一半,最多进行O(log n)
次比较。 - 空间复杂度:
O(1)
,只使用了常数个额外变量。
代码
/**
* @param {number} num
* @return {boolean}
*/
var isPerfectSquare = function (num) {
let left = 1,
right = num; // 初始化搜索范围
while (left <= right) {
const mid = Math.floor((left + right) / 2); // 计算中间值
const product = mid * mid; // 计算平方值
if (product === num) return true; // 如果找到完全平方数
else if (product > num) {
right = mid - 1; // 缩小搜索范围到左半部分
} else {
left = mid + 1; // 缩小搜索范围到右半部分
}
}
return false; // 如果未找到,返回 false
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 | 力扣 |
---|---|---|---|---|---|
69 | x 的平方根 | [✓] | 数学 二分查找 | 🟢 | 🀄️ 🔗 |
633 | 平方数之和 | 数学 双指针 二分查找 | 🟠 | 🀄️ 🔗 |