LeetCode 69. x 的平方根 Sqrt(x)(C语言)
题目描述:实现 int sqrt(int x) 函数。 计算并返回 x 的平方根,其中 x 是非负整数。 由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。 示例 1:输入: 4 输出: 2 示例 2:输入: 8 输出: 2 说明: 8 的平方根是 2.82842…, 由于返回类型是整数,小数部分将被舍去。 题目解答:方法1:暴力法:从1开始向后遍历,直至其平方大于x。 运行时间20ms左右,代码如下。 int mySqrt(int x) { if(x <= 0) return 0; long long i = 0; for(i = 1; ; i++) { if(i * i > x) break; } return i - 1; } 方法2:二分法可以减少遍历次数,利用二分法向合理的目标数逼近。 运行时间12ms左右,代码如下。 int mySqrt(int x) { if(x <= 0) return 0; if(x == 1) return 1; int l = 1,r = x / 2; long mid = 0,t = 0; while(l <= r) { mid = (l + r) / 2; t = mid * mid; if(t == x) return mid; else if(t > x) r = mid - 1; else l = mid + 1; } return r; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |