leetcode:367. 有效的完全平方数

leetcode:367. 有效的完全平方数 题目

来源：力扣（LeetCode）
链接：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

解法

• 库函数：sqrt，判断求sqrt后的值是否为整数即可
• python

class Solution:
	def isPerfectSquare(self, num: int) -> bool:
		return float.is_integer(pow(num, 0.5))

• c++

class Solution {
public:
    bool isPerfectSquare(int num) {
        int x = (int) sqrt(num);
        return x*x == num;
    }
};

• 循环: 循环i(i
• python

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        x = 1
        square = 1
        while square <= num:
            if square == num:
                return True
            x += 1
            square = x * x
        return False

• c++

class Solution {
public:
    bool isPerfectSquare(int num) {
        long i = 1;
        long square = 1;  // int not enough to cover
        while(square<=num)
        {
            if (square == num)
            {
                return true;
            }
            ++i;
            square = i * i;
        }
        return false;
    }   
};

• 二分法: 基于上述的循环法，因为是顺序的，可以采用二分查找法，更快的找到mid*mid==num的i值
• python

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

• c++

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


    }
};

注意
在c++语言中，要注意变量类型的取值范围

复杂度分析

• 时间复杂度：
  • 方法1: 未知，pow，sqrt函数的时空复杂度与cpu支持的指令集有关
  • 方法2:时间复杂度： O ( n ) O(sqrt{n}) O(n ​)，其中 n 为正整数num 的最大值。最多需要遍历 n + 1 sqrt{n} + 1 n ​+1 个正整数
  • 方法3: O ( l o g n ) O(logn) O(logn)，其中 n 为正整数num的最大值
• 空间复杂度：
  • 方法1: 未知
  • 方法2：O(1)
  • 方法3: O(1)