leetcode69 x 的平方根
文章目录
- 1. 解法
- 二分法
- 牛顿迭代
- 2. 原题 [69. x 的平方根 ](https://leetcode.cn/problems/sqrtx/)
1. 解法
二分法
题目变形为找到 f ( x ) = x 2 − c = 0 f(x)=x^2-c=0 f(x)=x2−c=0的根，其中 x x x是非负整数。由于 f ( 0 ) = − c ≤ 0 ， f ( c ) = c 2 − c ≥ 0 f(0)=-c\le0，f(c)=c^2-c\ge0 f(0)=−c≤0，f(c)=c2−c≥0，则 [ 0 , c ] [0,c] [0,c]之间必然存在一个根，使用二分法。
但是由于计算中会变成 c / x c/x c/x，防止除数为0，则从1开始
class Solution {
public int mySqrt(int x) {
if(x == 0){
return 0;
}
int l = 1;//左指针
int r = x;//右指针
int sqrt;//记录得到的算数平方根
int mid;//中间指针
while(l <= r){
mid = l + (r-l) / 2;
sqrt = x / mid;
if(sqrt == mid){
return mid;
}else if (sqrt < mid){
r = mid - 1;
}else{
l = mid + 1;
}
}
return r;
}
}
牛顿迭代
牛顿迭代公式： x n + 1 = x n − f ( x n ) / f ′ ( x n ) x_{n+1}=x_n-f(x_n)/f'(x_n) xn+1=xn−f(xn)/f′(xn)
class Solution {
public int mySqrt(int x) {
long sqrt = x;
while(sqrt * sqrt > x){
sqrt = (sqrt + x / sqrt) / 2;
}
return (int)sqrt;
}
}
2. 原题 69. x 的平方根
给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
**注意：**不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
示例 1：
输入：x = 4
输出：2
示例 2：
输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
提示：
- 0 < = x < = 2 31 − 1 0 <= x <= 2^{31} - 1 0<=x<=231−1