【LeetCode】第69题 X的平方根

题目:X的平方根

实现 int sqrt(int x) 函数。

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

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

示例 1:

1
2
输入: 4
输出: 2

示例 2:

1
2
3
4
输入: 8
输出: 2
说明: 8 的平方根是 2.82842...,
由于返回类型是整数,小数部分将被舍去。

解法1:二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/*
* @lc app=leetcode.cn id=69 lang=java
*
* [69] x 的平方根
* √ Accepted
* √ 1017/1017 cases passed (6 ms)
* √ Your runtime beats 90.28 % of java submissions
* √ Your memory usage beats 75.25 % of java submissions (33.6 MB)
*/
class Solution {
public int mySqrt(int x) {
if(x == 0) {
return 0;
}

if(x == 1){
return 1;
}

int start = 1;
// 将遍历上界指向x/2 + 1,x的平方根不可能大于x的一半
int end = x / 2 + 1 ;
int middle = 0;
while (start <= end) {
middle = ((end - start) >> 1) + start;
// 注意:此处大坑
// 防止越界 不要写成 middle * middle = x
if(middle == x / middle) {
return middle;
} else {
if (middle < x / middle) {
start = middle + 1;
} else {
end = middle - 1;
}
}
}
// 返回end,因为最后end一定小于等于start
return end;
}
}

解法2:牛顿迭代法

等学会再写吧,呜呜呜……

您的支持将让服务器运行更长久