Problem Description
给定一个正整数 num,编写一个函数,如果 num 是一个完全平方数,则返回 True,否则返回 False。
note
不要使用任何内置的库函数,如:sqrt
。
e.g.
- 示例 1:
- 输入:16
- 输出:True
- 示例 2:
- 输入:14
- 输出:False
Solution
暴力法
可以无限优化的方法,其优化的核心就在于循环的起始和终止,效率很低不考虑。
根区间&二分法
- Java 里 int 的最大值是 0x7fffffff,也就是 132-1(2147483647),大约 21 亿。最大值的平方根约等于 46340。那我不是根据整数的位数来得到一个计算的区间,这样不是能有效缩小循环的次数了吗?
- 比如 1 位数和 2 位数[10, 99],平方根一定是落在[1, 10),比如 3 位数[100, 999],平方根一定是落在[10, 32),比如 4 位数[1000, 9999],平方根一定是落在[31, 100);
- 当这个数很大的话(最大为 2147483647),相应的区间也会变大,但是区间最大的反而是 9 位数,因为 10 位数最大只到 2147483647;
- 我们根据整数的长度取得平方根的区间后可以根据二分查找法,将平均时间复杂度降低。
class Solution {
public static boolean isPerfectSquare(int num) {
int[] se = interval(String.valueOf(num).length());
int left = se[0];
int right = se[1];
while (true) {
int mid = left + (right - left) / 2;
if (mid * mid < num) {
if (right - left == 1) {
return false;
} else {
left = mid;
}
} else if (mid * mid == num) {
return true;
} else {
if (right - left == 1) {
return false;
} else {
right = mid;
}
}
}
}
public static int[] interval(int len) {
int start;
int end;
switch (len) {
case 3:
start = 10;
end = 32;
break;
case 4:
start = 31;
end = 100;
break;
case 5:
start = 100;
end = 317;
break;
case 6:
start = 316;
end = 1000;
break;
case 7:
start = 1000;
end = 3163;
break;
case 8:
start = 3162;
end = 10000;
break;
case 9:
start = 10000;
end = 31623;
break;
case 10:
start = 31622;
end = 46341;
break;
default:
start = 1;
end = 10;
}
return new int[]{start, end};
}
}
二分法有一个很需要注意的点:就是求中间值的计算公式。一般最好不要直接这样做:(left + right) / 2
,因为很有可能在 left + right
的过程中就溢出了,算出来是负数的。改成 long 类型或者这样算:left + (right - left) / 2
。
两个点优化之后,即使一个很大的数字也不需要经过几次的查找便可知道是否是完全平方数。以上算法的时间复杂度为 O(1) + O(log2n) = O(log2n)。
欢迎来到这里!
我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。
注册 关于