LeetCode 题解 Swift 有效的完全平方数_Swift文章/教程_其他教程_编程语言

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

2023-02-07 学习力0

核心提示：目录题目方法一：使用内置的库函数思路及解法复杂度分析方法二：暴力思路及解法代码复杂度分析方法三：二分查找思路及解法细节代码复杂度分析题目给定一个正整数 num，编写一个函数，如果 num 是一个完全平方数，则返回 true，否则返回 false。进阶：不要使

题目

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

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

示例 1：

输入： num = 16

输出： true

示例 2：

输入： num = 14

输出： false

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

思路及解法

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

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

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

复杂度分析

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

方法二：暴力

思路及解法

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

代码

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
    }
}

复杂度分析

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

方法三：二分查找

思路及解法

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

细节

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

代码

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)。

以上就是LeetCode 题解 Swift 有效的完全平方数的详细内容，更多关于Swift 有效完全平方数的资料请关注其它相关文章！

原文地址：https://juejin.cn/post/7146026724856168461

免责声明：本文仅代表作者个人观点，与乐学笔记（本网）无关。其原创性以及文中陈述文字和内容未经本站证实，对本文以及其中全部或者部分内容、文字的真实性、完整性、及时性本站不作任何保证或承诺，请读者仅作参考，并请自行核实相关内容。
本网站有部分内容均转载自其它媒体，转载目的在于传递更多信息，并不代表本网赞同其观点和对其真实性负责，若因作品内容、知识产权、版权和其他问题，请及时提供相关证明等材料并与我们留言联系，本网站将在规定时间内给予删除等相关处理.