一起学算法-367. 有效的完全平方数

一、题目

LeetCode-367. 有效的完全平方数
链接：https://leetcode-cn.com/problems/valid-perfect-square/

难度：简单

给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。

进阶：不要 使用任何内置的库函数，如 sqrt 。

示例 1：
输入：num = 16
输出：true

示例 2：
输入：num = 14
输出：false
 

提示：
1 <= num <= 2^31 - 1

二、解题思路

该题与一起学算法-69. x 的平方根非常类似，题目的解可能存在于0到num之间，我们可以通过暴力枚举或者二分查找来找到题目的解。

三、实现过程

c++

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

PHP

class Solution {

    /**
     * @param Integer $num
     * @return Boolean
     */
    function isPerfectSquare($num) {
        $left = 0;
        $right = $num;
        while($left <= $right){
            $mid = (int)(($left + $right) / 2);
            if($mid*$mid == $num){
                return true;
            }else if($mid*$mid < $num){
                $left = $mid + 1;
            }else{
                $right = $mid - 1;
            }
        }
        return false;
    }
}

JavaScript

/**
 * @param {number} num
 * @return {boolean}
 */
var isPerfectSquare = function(num) {
        var left = 0,right = num,mid;
        while(left <= right){
            mid = Math.floor((left + right) / 2);
            if(mid*mid == num){
                return true;
            }else if(mid*mid < num){
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }
        return false;
};

四、小结

1. 时间复杂度：O(logN)，其中N是num的大小
2. 空间复杂度：O(1)