【題目描述】
實(shí)現(xiàn) int sqrt(int x) 函數(shù)据途。
計(jì)算并返回 x 的平方根绞愚，其中 x 是非負(fù)整數(shù)。
由于返回類型是整數(shù)颖医，結(jié)果只保留整數(shù)的部分位衩，小數(shù)部分將被舍去。
【示例1】
輸入: 4
輸出: 2
【示例2】
輸入: 8
輸出: 2
說明: 8 的平方根是 2.82842...,
由于返回類型是整數(shù)熔萧，小數(shù)部分將被舍去糖驴。
【思路1】
1、要實(shí)現(xiàn)sqrt開平方佛致，反過來想 ii == num
2贮缕、小數(shù)將被舍棄，也就是說 當(dāng) ii > num 時(shí) 返回i-1即可俺榆，i*i = num 返回i
3感昼、時(shí)間復(fù)雜度O(n)
4、空間復(fù)雜度O(1)
代碼實(shí)現(xiàn)：
func mySqrt(_ x: Int) -> Int {
for i in 0...x {
if i*i == x {
return i
}
if i*i > x {
return i-1
}
}
return 0
}
【思路2】
1罐脊、雙指針往中間湊
2定嗓、時(shí)間復(fù)雜度O(logn)
3蜕琴、空間復(fù)雜度O(1)
代碼實(shí)現(xiàn)：
func mySqrt(_ x: Int) -> Int {
if x == 0 {
return 0
}
var left = 0,right = x/2+1
while left <= right {
let mid = (left+right)/2
let product = mid*mid
if product == x {
return mid
} else if product < x {
left = mid+1
} else {
right = mid-1
}
}
return right
}
