Easy

题目描述

给你一个正整数 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

解题思路

这道题要求判断一个数是否为完全平方数，有几种解法：

解法一：二分查找（推荐）

由于完全平方数的平方根一定是整数，我们可以用二分查找在 [1, num] 范围内寻找可能的平方根。设置左边界为1，右边界为num，每次取中间值mid，计算 mid * mid：

  • 如果等于num，说明找到了完全平方根
  • 如果小于num，说明平方根在右半部分
  • 如果大于num，说明平方根在左半部分

需要注意整数溢出问题，可以通过 mid > num / mid 来避免。

解法二：牛顿法

利用牛顿迭代法求平方根，公式为 x = (x + num/x) / 2，当收敛时检查是否为整数。

解法三：数学性质

利用完全平方数的性质：连续奇数之和等于完全平方数。即 1 + 3 + 5 + ... + (2n-1) = n²。

二分查找法效率高且易理解，时间复杂度为O(log n)，是最优解法。

代码实现

class Solution {
public:
    bool isPerfectSquare(int num) {
        long left = 1, right = num;
        
        while (left <= right) {
            long mid = left + (right - left) / 2;
            long square = mid * mid;
            
            if (square == num) {
                return true;
            } else if (square < num) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return false;
    }
};

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        left, right = 1, num
        
        while left <= right:
            mid = (left + right) // 2
            square = mid * mid
            
            if square == num:
                return True
            elif square < num:
                left = mid + 1
            else:
                right = mid - 1
        
        return False

public class Solution {
    public bool IsPerfectSquare(int num) {
        long left = 1, right = num;
        
        while (left <= right) {
            long mid = left + (right - left) / 2;
            long square = mid * mid;
            
            if (square == num) {
                return true;
            } else if (square < num) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return false;
    }
}

var isPerfectSquare = function(num) {
    let left = 1;
    let right = num;
    
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        let square = mid * mid;
        
        if (square === num) {
            return true;
        } else if (square < num) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return false;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

解法时间复杂度空间复杂度
二分查找O(log n)O(1)
牛顿法O(log n)O(1)
奇数和法O(√n)O(1)

相关题目