367. 有效的完全平方数
题目描述
给你一个正整数 num
。如果 num
是一个完全平方数,则返回 true
,否则返回 false
。
完全平方数 是一个可以写成某个整数的平方的整数。换句话说,它可以写成某个整数和自身的乘积。
不能使用任何内置的库函数,如 sqrt
。
示例 1:
输入:num = 16 输出:true 解释:返回 true ,因为 4 * 4 = 16 且 4 是一个整数。
示例 2:
输入:num = 14 输出:false 解释:返回 false ,因为 3.742 * 3.742 = 14 但 3.742 不是一个整数。
提示:
1 <= num <= 231 - 1
解法
方法一:二分查找
不断循环二分枚举数字,判断该数的平方与 num
的大小关系,进而缩短空间,继续循环直至 $left \lt right$ 不成立。循环结束判断 $left^2$ 与 num
是否相等。
时间复杂度:$O(logN)$。
1 2 3 4 5 6 7 8 9 10 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
1 2 3 4 5 6 7 8 9 10 11 12 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
|
方法二:转换为数学问题
由于 n² = 1 + 3 + 5 + ... + (2n-1)
,对数字 num
不断减去 $i$ (i = 1, 3, 5, ...
) 直至 num
不大于 0,如果最终 num
等于 0,说明是一个有效的完全平方数。
时间复杂度:$O(sqrt(N))$。
1 2 3 4 5 6 7 |
|
1 2 3 4 5 6 7 8 |
|
1 2 3 4 5 6 7 |
|
1 2 3 4 5 6 |
|
1 2 3 4 5 6 7 8 |
|
1 2 3 4 5 6 7 8 9 10 |
|