LeetCode 题解 Swift 有效的完全平方数,
投稿于 被查看 15910 次 评论:73
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(logn),其中 n为正整数 num 的最大值。
- 空间复杂度:O(1)。
以上就是LeetCode 题解 Swift 有效的完全平方数的详细内容,更多关于Swift 有效完全平方数的资料请关注3672js教程其它相关文章!
您可能感兴趣的文章:- 前端算法题解leetcode49-字母异位词分组
- 前端算法题解 leetcode50-Pow(x, n)
- 前端算法leetcode109题解有序链表转换二叉搜索树
- 前端算法题解leetcode114二叉树展开为链表
- LeetCode 刷题 Swift 两个数组的交集
- 前端算法题解leetcode36-有效的数独示例
用户评论