题目描述

实现 int sqrt(int x) 函数。

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

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

示例1:

输入: 4
输出: 2

示例2:

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

暴力版本

// 暴力解法
func mySqrt(x int) int {
	for i := 0; i <= x; i++ {
		res := i * i
		if res == x {
			return i
		} else if res > x {
			return i - 1
		}
	}
	return -1
}

二分查找

//在有序数组中,找到最后一个小于等于给定值的数
func mySqrt2(x int) int {
	low, high := 0, x
	for low <= high {
		//防止大数相加溢出
		//位运算更高效
		mid := low + (high-low)>>1
		product := mid * mid
		if product > x {
			high = mid - 1
		} else {
			if (mid == x) || (mid+1)*(mid+1) > x {
				//遍历最后一个数 || 下一个数大于目标值
				return mid
			}
			//下一个数小于等于目标值,所以mid不是最后一个数
			low = mid + 1
		}
	}
	return -1
}

二分查找思路

  • 相当于从0-x中找到最后一个平方<=x的整数
  • 我们求解的是最后一个小于等于给定值的元素,所以当 product<=x时,需要确认 mid+1 的平方>x
  • 如果 mid+1 的平方 <= x ,说明mid肯定不是最后一个,更新low

GitHub

  • 源码传送门
  • 项目中会提供各种数据结构及算法的Golang实现, LeetCode解题思路及答案
参考资料

leetcode 69. x 的平方根

极客时间 数据结构与算法之美

本文为原创文章,转载注明出处,欢迎扫码关注公众号 tomorrowwu 或者网站https://lovecoding.club,第一时间看后续精彩文章,觉得好的话,顺手分享到朋友圈吧,感谢支持。

image