【题目描述】
给定一个正整数 num，编写一个函数，如果 num 是一个完全平方数，则返回 True，否则返回 False。
说明：不要使用任何内置的库函数，如 sqrt。
【示例1】
输入：16
输出：True
【示例2】
输入：14
输出：False
【思路1】
1、时间复杂度O(n)
2、空间复杂度O(1)
func isPerfectSquare(_ num: Int) -> Bool {
if num == 0 { return false }
for i in 1...num {
if i*i > num {
return false
} else if i*i == num {
return true
}
}
return false
}
【思路2】
1、二分法
2、时间复杂度O(logn)
3、空间复杂度O(1)
代码实现：
func isPerfectSquare(_ num: Int) -> Bool {
if num == 0 { return false }
var left = 0
var right = num
while left <= right {
let mid = (left+right)/2
let product = mid*mid
if product == num {
return true
} else if product > num {
right = mid-1
} else {
left = mid+1
}
}
return false
}
【思路3】
1、数学公式 1+3+5+7+...+2n-1 = n^2 完全平方数是前n项连续奇数的和
2、时间复杂度O(n)
3、空间复杂度O(1)
代码实现：
func isPerfectSquare(_ num: Int) -> Bool {
if num == 0 { return false }
var i = 1
var sum = num
while sum > 0 {
sum-=i
i+=2
}
return sum == 0
}
