
问题
实现 int sqrt(int x) 函数。
计算并返回 x 的平方根,其中 x 是非负整数。
由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。
输入: 4
输出: 2
输入: 8
输出: 2
说明: 8 的平方根是 2.82842…, 由于返回类型是整数,小数部分将被舍去。
Implement int sqrt(int x).
Compute and return the square root of x, where x is guaranteed to be a non-negative integer.
Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.
Input: 4
Output: 2
Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842…, and since the decimal part is truncated, 2 is returned.
示例
public class Program { public static void Main(string[] args) { var n = 8; var res = MySqrt(n); Console.WriteLine(res); n = 168; res = MySqrt2(n); Console.WriteLine(res); n = 69; res = MySqrt3(n); Console.WriteLine(res); Console.ReadKey(); } private static int MySqrt(int x) { //耍赖 return (int)(Math.Sqrt(x)); } private static int MySqrt2(int x) { //二分逼近,最后收敛于sqrt(x) long res = x; while(res * res > x) { res = (res + x / res) / 2; } return (int)res; } private static int MySqrt3(int x) { //魔数0x5f3759df,这个解法自行百度 //另外,这个解法LeetCode未AC,因为不支持unsafe var i = 0L; var num1 = 0F; var num2 = 0F; const float f = 1.5F; num1 = x * 0.5F; num2 = x; unsafe { i = *(long*)&num2; i = 0x5f3759df - (i >> 1); num2 = *(float*)&i; } num2 = num2 * (f - (num1 * num2 * num2)); num2 = num2 * (f - (num1 * num2 * num2)); return (int)(x * num2); } }
以上给出3种算法实现,以下是这个案例的输出结果:
2 12 8
分析:
MySqrt 的时间复杂度依赖于运行库的实现,MySqrt2 的时间复杂度为: ,MySqrt3 的时间复杂度为:
。
本文由 .Net中文网 原创发布,欢迎大家踊跃转载。
转载请注明本文地址:https://www.byteflying.com/archives/3848。