题目:给定一个正整数 num,编写一个函数,判断如果 num 是一个完全平方数,则返回 true,否则返回 false。注意:不可使用编程语言提供的类库函数,比如Java语言的 Math 类的 sqrt 函数。本篇经验将分享如何通过二分查找算法判断一个数字是否是有效的完全平方数。
工具/原料
1
Eclipse
2
JDK1.8
方法/步骤
1
实现二分查找算法,算法思想:如果一个数字 num 是一个完全平方数,则其平方根只能出现在 1 - num/2 之间,通过二分查找算法,判断这个区间内是否有一个数字的平方等于 num,如果有,则返回 true,否则返回 false,图示代码。
2
编写本地测试方法。
4
平台提交算法,测试通过。
5
算法总结:算法通过使用二分查找,时间复杂度为 O(logn),n 为判断的目标数字,如果通过遍历来判断是否是完全平方数,则其时间复杂度为 O(n)。
注意事项
如果算法涉及到int类型的大数相乘,则一定要考虑结果是否会溢出,是否需要通过long来表示结果。
上一篇:复式楼一分为二
下一篇:多功能护理床分为几种?