leetcode-69.x的平方根
leetcode-69.x的平方根
Points
题意
实现
int sqrt(int x)函数。计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
示例 1:
输入: 4 输出: 2示例 2:
输入: 8 输出: 2 说明: 8 的平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。示例 3:
输入: 2147395600 输出: 46340
算法-1---牛顿迭代
用时：16ms
复杂度：应该是小于二分的。代值验证了一下，但不完全。
递推公式：
Xn+1 = Xn - (F(x) / F'(x)), 这相当于是求解 r2 = x, 即 F(r) = r2 - x
化简得：Xn+1 = 1/2 （Xn - x/X(n)）
不明白的话，请留言或者自行参考文首连接。
code
1 class Solution { 2 public: 3 int mySqrt(int x) { 4 long ans = x;; 5 while(true) 6 { 7 if(ans*ans <= x && (ans+1)*(ans+1) > x) 8 break; 9 else 10 { 11 ans = long(0.5*(ans + x/ans)); 12 } 13 } 14 return ans; 15 } 16 };
算法-2---二分查找
用时：16ms
复杂度：O(log2n)
二分查找，是固定套路，套就完了，但是要注意的是，搞清楚取 右值 的原因。
code
1 class Solution { 2 public: 3 int mySqrt(int x) { 4 long left = 0, right = x, mid; 5 while(left <= right) 6 { 7 mid = (left + right)/2; 8 if(mid * mid > x) 9 right = mid -1; 10 else if(mid * mid < x) 11 left = mid + 1; 12 else 13 return mid; 14 } 15 return right; 16 } 17 };
投递柠檬微趣等公司10个岗位 >
