判断一个自然数是否是某个数的平方

判断一个自然数是否是某个数的平方。

51CTO上的参考答案如下 写道

假设待判断的数字是 N。

方法1：

遍历从1到N的数字，求取平方并和N进行比较。

如果平方小于N，则继续遍历；如果等于N，则成功退出；如果大于N，则失败退出。

复杂度为O(n^0.5)。

方法2：

使用二分查找法，对1到N之间的数字进行判断。

复杂度为O(log n)。

方法3：

由于

(n+1)^2
=n^2 + 2n + 1，
= ...
= 1 + (2*1 + 1) + (2*2 + 1) + ... + (2*n + 1)

注意到这些项构成了等差数列（每项之间相差2）。

所以我们可以比较 N-1， N - 1 - 3， N - 1 - 3 - 5 ... 和0的关系。

如果大于0，则继续减；如果等于0，则成功退出；如果小于 0，则失败退出。

复杂度为O(n^0.5)。不过方法3中利用加减法替换掉了方法1中的乘法，所以速度会更快些。

方法3不是很看得懂。。。

我的想法 写道

public static boolean getResult(int number) {
	int in = number;
	int num = 0;
	for (int i = 2; i <= in;) {
		if (in % i == 0) {
			in = in / i;
			num++;
			if (in == 1 && num % 2 == 0) {
				return true;
			}
		} else {
			if (num % 2 != 0) {
				return false;
			}
			i++;
		}
	}
	return false;
}

不知道有木有更好的算法