Sorry, your browser cannot access this site
This page requires browser support (enable) JavaScript
Learn more >

方法一:二分

  • 时间复杂度:O(logN)
  • 空间复杂度:O(1)

注意点:

  1. mid*mix > x的时候容易溢出,改成mid > x/mid
  2. mid := (l+r)>>1的时候也容易溢出,改成mid := l + (r-l)>>1
不保留小数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//不保留小数
func Sqrt(x int) int {

if x <= 0 {
return 0
}

l, r := 1, x-1
for l <= r {
mid := l + (r-l)>>1
if mid > x/mid {
r = mid - 1
} else if mid < x/mid { //Tips:写成x/mid用来确认不会溢出
l = mid + 1
} else {
return mid
}
}

return r
}

保留小数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//返回一个数的整数:保留4位小数
func SqrtToFloat(x int) float64 {
if x == 0 {
return 0
}

l, r := float64(1), float64(x-1)
for l <= r {
mid, _ := strconv.ParseFloat(fmt.Sprintf("%.4f", l+(r-l)/2), 64)
//保留小数
if mid > float64(x)/mid {
r = mid - 0.0001
} else if mid < float64(x)/mid {
l = mid + 0.0001
} else {
return mid
}
}
r, _ = strconv.ParseFloat(fmt.Sprintf("%.4f", r), 64)
return r
}

方法二:牛顿迭代

思路:假设我们要求的是整数c的平方根,那么平方根也就是$ x^2 - c = 0 $ 的解(因为曲线是$ y = x_2 - c $),假设此时我们在$(x_0, {x_0}^2-c)$,也就是曲线上的点

步骤如下:

  1. 过该点做切线,这个切线是不断逼近于$ y = x_2 - c $这个曲线与x轴的交点(也就是我们要求的),切线斜率求导可得为$ 2 * x_0 $,并且经过$(x_0, {x_0}^2-c)$,所以我们切线方程为 $ y = 2x_0*x-x_0^2-c $
  2. 切线与x轴交点的横坐标为$ \frac{x_0}{2} + \frac{c}{2x_0} $,下次我们就让$ x0 $ 移动到这个横坐标,然后开始下一次迭代,直到我们上一次迭代与下一次迭代的x的差距小于我们规定的值比如$ 1e-7 $,我们就认为迭代结束,然后返回结果
  • 时间复杂度:O(log x),此方法是二次收敛的,相较于二分查找更快。
  • 空间复杂度:O(1)。
不保留小数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//牛顿迭代法,返回整数
func SqrtII(x int) int {

c, x0 := float64(x), float64(x)

for {
//每次的切线方程都是y=2x0*x-x0^2
xi := x0/2 + c/(2*x0)
if math.Abs(xi-x0) < 1e-7 {
break
}
x0 = xi
}

return int(x0)
}
保留小数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//牛顿迭代法保留4位小数
func SqrtToFloatII(x int) float64 {
c, x0 := float64(x), float64(x)

for {
//每次的切线方程都是y=2x0*x-x0^2
xi := x0/2 + c/(2*x0)
if math.Abs(xi-x0) < 1e-7 {
break
}
x0 = xi
}
fmt.Println(fmt.Sprintf("%.4f", x0))
ret, _ := strconv.ParseFloat(fmt.Sprintf("%.4f", x0), 64)
return ret
}

评论