367. 有效的完全平方数

🟢   🔖  数学 二分查找  🔗 力扣 LeetCode

题目

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 <= 2^31 - 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 <= 2^31 - 1

解题思路

我们可以利用 二分查找 来高效判断 num 是否为完全平方数。

如果使用暴力法，从 1 到 num 遍历所有可能的整数，并判断其平方是否等于 num，这种方法的时间复杂度为 O(sqrt(num))，对于较大的 num 效率较低。

使用二分查找算法，可以在对数时间内找到 num 是否为完全平方数。假设 x 是 num 的平方根，我们可以限制 x 的取值范围在 [1, num]。通过二分查找，逐步逼近 x，检查中间值 mid 的平方是否等于 num，并根据结果缩小搜索范围。

1. 初始化 left = 1 和 right = num，定义搜索范围。

2. 计算中间值 mid = Math.floor((left + right) / 2)。

3. 比较 mid * mid 和 num：

   • 如果 mid * mid == num，返回 true。
   • 如果 mid * mid > num，说明平方根在左半部分，调整右边界：right = mid - 1。
   • 如果 mid * mid < num，说明平方根在右半部分，调整左边界：left = mid + 1。

4. 如果搜索完成后未找到满足条件的整数，返回 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	平方数之和		数学 双指针 二分查找	🟠	🀄️ 🔗