跳至主要內容

367. 有效的完全平方数


367. 有效的完全平方数

🟢   🔖  数学 二分查找  🔗 力扣open in new window LeetCodeopen in new window

题目

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 是否为完全平方数。

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

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

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

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

  3. 比较 mid * midnum

    • 如果 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
};

相关题目

题号标题题解标签难度力扣
69x 的平方根[✓]数学 二分查找🟢🀄️open in new window 🔗open in new window
633平方数之和数学 双指针 二分查找🟠🀄️open in new window 🔗open in new window