Problem Description
给定一个正整数 num，编写一个函数，如果 num 是一个完全平方数，则返回 True，否则返回 False。
note
不要使用任何内置的库函数，如：sqrt。
e.g.
Solution
1. 暴力法
可以无限优化的方法，其优化的核心就在于循环的起始和终止，效率很低不考虑。
2. 根区间&二分法
- 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；
- 我们根据整数的长度取得平方根的区间后可以根据二分查找法，将平均时间复杂度降低。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
| 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};
}
}
|
注意：二分法有一个很需要注意的点，就是求中间值mid的计算公式。一般最好不要直接这样做：(left + right) / 2，因为很有可能在left + right的过程中就溢出了，算出来是负数的。改成long类型或者这样算：left + (right - left) / 2。
两个点优化之后，即使一个很大的数字也不需要经过几次的查找便可知道是否是完全平方数。以上算法的时间复杂度为O(1) + O(log2n) = O(log2n)。