給定一個非負整數 x ，計算并返回 x 的平方根，即實現 int sqrt(int x) 函數。

正數的平方根有兩個，隻輸出其中的正數平方根。

如果平方根不是整數，輸出隻保留整數的部分，小數部分将被舍去。

示例 1:輸入: x = 4 輸出: 2

示例 2:輸入: x = 8 輸出: 2

解釋: 8 的平方根是 2.82842...，由于小數部分将被舍去，所以返回 2

提示:0 <= x <= 231 - 1

注意：本題與主站 69 題相同：

1、内置函數；時間複雜度O(log(n))，空間複雜度O(1)

func mySqrt(x int) int { result := int(math.Sqrt(float64(x))) return result }

2、内置函數；時間複雜度O(log(n))，空間複雜度O(1)

func mySqrt(x int) int { result := math.Floor(math.Sqrt(float64(x))) return int(result) }

3、牛頓疊代法；時間複雜度O(log(n))，空間複雜度O(1)

func mySqrt(x int) int { result := x for result*result > x { result = (result x/result) / 2 } return result }

4、二分查找；時間複雜度O(log(n))，空間複雜度O(1)

func mySqrt(x int) int { left := 1 right := x for left <= right { mid := (left right) / 2 if mid == x/mid { return mid } else if mid < x/mid { left = mid 1 } else { right = mid - 1 } } if left*left <= x { return left } else { return left - 1 } }

5、遍曆；時間複雜度O(n)，空間複雜度O(1)

func mySqrt(x int) int { result := 0 for i := 1; i <= x/i; i { if i*i == x { return i } result = i } return result }

Easy題目，題目同leetcode 69.x的平方根

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!