9. Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x, where x is guaranteed to be a non-negative integer.

Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.

Example 1:

1
2
Input: 4
Output: 2

Example 2:

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

69. x 的平方根

实现 int sqrt(int x) 函数。

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

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

示例 1:

1
2
输入: 4
输出: 2

示例 2:

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

解法:

方法一:内置函数法

1
2
3
func mySqrt(_ x: Int) -> Int {
return Int(sqrt(Double(x)))
}

方法二 :二分法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func mySqrt(_ x: Int) -> Int {
if x == 0 {
return 0
}
var left = 0
var right = x / 2 + 1//开平方以后的值肯定小于 x / 2 + 1
var mid = 0
var res = 0

while left <= right {
mid = (left + right) / 2
res = mid * mid
if res == x {
return mid
} else if res > x {
right = mid - 1
} else {
left = mid + 1
}
}
return right
}

方法三 :牛顿迭代法(牛顿-拉弗森方法)

1
2
3
4
5
6
7
8
9
10
func mySqrt(_ x: Int) -> Int {
if x == 0 {
return 0
}
var res = x
while res * res > x {
res = (res + x / res) / 2
}
return res
}

对于牛顿迭代法先前也是不了解,看到别人的解法中有这么一个觉得思路还是蛮好的,想了解的同学可以看看知乎上如何通俗易懂地讲解牛顿迭代法求开方?数值分析?这个回答,讲的还是很详细的。

结果:

方法时间复杂度(T(n))空间复杂度(S(n))执行用时(ms)内存消耗(MB)
方法一O(1)O(1)1620.2
方法二O(logn)O(1)1620.4
方法三-O(1)2020.7

根据 LeetCode 上面的题目每日学习算法,持续更新,更多思路解法尽在 Daily-learning-algorithm,欢迎 star !

若您觉得我的文章对你有帮助,欢迎点击上方按钮对我打赏!
------------- 本文结束 感谢您的阅读 -------------