LeetCode 题解 Swift 有效的完全平方数

题目

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

进阶:不要 使用任何内置的库函数,如 sqrt

示例 1:

输入: num = 16

输出: true

示例 2:

输入: num = 14

输出: false

方法一:使用内置的库函数

思路及解法

根据完全平方数的性质,我们只需要直接判断 num\textit{num}num 的平方根 xxx 是否为整数即可。对于不能判断浮点数的值是否等于整数的语言,则可以通过以下规则判断:

class Solution {
 func isPerfectSquare(_ num: Int) -> Bool {
 let x: Int = Int(sqrt(Double(num)))
 return x * x == num
 }
}

复杂度分析

代码中使用的 pow 函数的时空复杂度与 CPU 支持的指令集相关,这里不深入分析。

方法二:暴力

思路及解法

代码

class Solution {
 func isPerfectSquare(_ num: Int) -> Bool {
 var x: Int = 1
 var square: Int = 1
 while square <= num {
 if square == num {
 return true
 }
 x += 1
 square = x * x
 }
 return false
 }
}

复杂度分析

方法三:二分查找

思路及解法

细节

代码

class Solution {
 func isPerfectSquare(_ num: Int) -> Bool {
 var left: Int = 0
 var right: Int = num
 while left <= right {
 let mid = (right - left) / 2 + left
 let square = mid * mid
 if square < num {
 left = mid + 1
 } else if square > num {
 right = mid - 1
 } else {
 return true
 }
 }
 return false
 }
}

复杂度分析

  • 时间复杂度:O(log⁡n),其中 n为正整数 num 的最大值。
  • 空间复杂度:O(1)。
作者:晨曦_iOS

%s 个评论

要回复文章请先登录注册