
问题
给定一个整数,写一个函数来判断它是否是 3 的幂次方。
输入: 27
输出: true
输入: 0
输出: false
输入: 9
输出: true
输入: 45
输出: false
进阶:你能不使用循环或者递归来完成本题吗?
Given an integer, write a function to determine if it is a power of three.
Input: 27
Output: true
Input: 0
Output: false
Input: 9
Output: true
Input: 45
Output: false
Follow up:Could you do it without using any loop / recursion?
示例
public class Program { public static void Main(string[] args) { var n = 25; var res = IsPowerOfThree(n); Console.WriteLine(res); n = 16; res = IsPowerOfThree2(n); Console.WriteLine(res); n = 27; res = IsPowerOfThree3(n); Console.WriteLine(res); Console.ReadKey(); } private static bool IsPowerOfThree(int n) { //先看原值是否能被3整除 //若不能整除,不是3的幂; //若能整除,继续往下,直接<=1时为止 //最后判断值是否为1即可 while(n % 3 == 0 && (n /= 3) > 1) { } return n == 1; } private static bool IsPowerOfThree2(int n) { //负数肯定不满足题意 if(n <= 0) return false; //找到整型范围内最大的3的幂 //var maxPower = (int)Math.Pow(3, (int)(Math.Log10(int.MaxValue) / Math.Log10(3))); var maxPower = 1162261467; //这个值是否能被n整除 return maxPower % n == 0; } private static bool IsPowerOfThree3(int n) { //基于高中数学的一些技巧 var x = Math.Log10(n) / Math.Log10(3); //这种解法有点赖皮,仅给大家一些思路吧 //IDE给出的警告请无视 return (int)x - x == 0; } }
以上给出3种算法实现,以下是这个案例的输出结果:
False False True
分析:
显而易见,IsPowerOfThree 的时间复杂度为: ,IsPowerOfThree2 和IsPowerOfThree3 的时间复杂度为:
。
本文由 .Net中文网 原创发布,欢迎大家踊跃转载。
转载请注明本文地址:https://www.byteflying.com/archives/3867。