題目連結: https://leetcode.com/problems/sqrtx/
題目:
Given a non-negative integer x
, compute and return the square root of x
.
Since the return type is an integer, the decimal digits are truncated, and only the integer part of the result is returned.
Note: You are not allowed to use any built-in exponent function or operator, such as pow(x, 0.5)
or x ** 0.5
.
解法一: (Time complexity: O(n))
// test case:
// x: 0
// x: 1
// x: 4
// x: 8
func mySqrt(_ x: Int) -> Int {
if x == 0 { return 0 }
var result = 0
while (result + 1) * (result + 1) <= x {
result += 1
}
return result
}
解法二: (Time complexity: O(logn))
Use Binary search
// test case:
// x: 0
// x: 1
// x: 4
// x: 8
func mySqrt(_ x: Int) -> Int {
var start = 0
var end = x
while start < end {
var mid = (start + end) / 2
if mid * mid == x {
start = mid
break
} else if mid * mid > x {
end = mid - 1
} else {
start = mid + 1
}
}
return start * start > x ? start - 1 : start
}