
问题
给定一个正整数 num,编写一个函数,如果 num 是一个完全平方数,则返回 True,否则返回 False。
说明:不要使用任何内置的库函数,如 sqrt。
输入:16
输出:True
输入:14
输出:False
Given a positive integer num, write a function which returns True if num is a perfect square else False.
Note: Do not use any built-in library function such as sqrt.
Input: 16
Output: true
Input: 14
Output: false
示例
public class Program { public static void Main(string[] args) { var n = 25; var res = IsPerfectSquare(n); Console.WriteLine(res); n = 17; res = IsPerfectSquare2(n); Console.WriteLine(res); n = 256; res = IsPerfectSquare3(n); Console.WriteLine(res); Console.ReadKey(); } private static bool IsPerfectSquare(int num) { //耍赖 var squard = Math.Sqrt(num); return (int)squard - squard == 0; //return Math.Sqrt(num) % 1 == 0; } private static bool IsPerfectSquare2(int num) { //完全平方数的差都为奇数,即1,3,5,7,9... //完全平方数是n个奇数的和 for(var i = 1; num > 0; i += 2) { num -= i; } return num == 0; } private static bool IsPerfectSquare3(int num) { //二分逼近,最后收敛于sqrt(x) long res = num; while(res * res > num) { res = (res + num / res) / 2; } return (int)(res * res) == num; } }
以上给出3种算法实现,以下是这个案例的输出结果:
True False True
分析:
IsPerfectSquare 的时间复杂度依赖于运行库的实现,IsPerfectSquare2 的时间复杂度为: ,IsPerfectSquare3 的时间复杂度为:
。
本文由 .Net中文网 原创发布,欢迎大家踊跃转载。
转载请注明本文地址:https://www.byteflying.com/archives/3869。