1-今日一扣-69-easy-二分法、牛顿法-sqrt实现

实现开方

leetcode

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根，其中 x 是非负整数。

由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

Example 1:

Input: 4 Output: 2

Example 2:

Input: 8 Output: 2 Explanation: The square root of 8 is 2.82842…, and since the decimal part is truncated, 2 is returned.

解答

暴力法

无脑迭代，略。

二分法查找-常规

class Solution { public int mySqrt(int x) { int left = 0; //从0开始 int right = x; //到x结束 int ans = -1; //初始化为-1,不会影响正常结果 while(left <= right ) { //注意二分法终止条件是left > right int mid = (left + right)/2; if((long)mid *mid >x){ //在left ... mid-1之间 right = mid -1; }else{// 在mid+1...right之间 left = mid + 1; ans = mid; //记录偏左侧答案。 } } return ans; } }

注意：

循环的终止条件 left<=right两个整形相乘，可能越界，结果要用long存储ans记录答案，取左侧的方法。时间复杂度$O(\log x)$，查找的次数。空间复杂度O（1）

牛顿法

牛顿法是一种通过迭代快速寻找函数零点的方法。 假设该题的函数为

$$y(x)=x^2-C$$ 就变成了寻找函数y的零点问题。 具体理论解释转到官网解析

class Solution { public int mySqrt(int x) { if (x == 0) { return 0; } double C = x, x0 = x; //构造y(x) = x^2 - c while (true) { double xi = 0.5 * (x0 + C / x0); //下一个x的位置。 if (Math.abs(x0 - xi) < 1e-7) { //是否符合误差范围 break; } x0 = xi; //迭代 } return (int)x0; //转成整数。 } } 作者：LeetCode-Solution 链接：https://leetcode-cn.com/problems/sqrtx/solution/x-de-ping-fang-gen-by-leetcode-solution/ 来源：力扣（LeetCode）

注：

空间复杂度O(1)，时间复杂度$O(\log x)$, 二次收敛，快于二分法。选择C = X确保正的0点在左侧。不会取到负的迭代结束条件是一个极小的非负数，通常取$10^{-6}$$10^{-7}$

例如求$\sqrt{2}$的近似解。使用牛顿法可以从2开始猜。精确的位数可以由误差来控制。