LeetCode069-x的平方根-easy

书旅 · · 132 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。
标签:二分
题目:x的平方根
题号:69
题干:实现 int sqrt(int x) 函数。计算并返回 x 的平方根,其中 x 是非负整数。由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去

示例1:
输入: 4
输出: 2

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

原题比较简单,因此这里做简单的变形,求x的平方根,要求可以获取指定精度的结果

示例:
输入:8 0.000001
输出:2.828427
说明:0.000001表示精确到小数点后六位

思路:

  • 要求x的平方根,最容易想到的就是从1到x,一个一个的试,这种方法的时间复杂度是O(n),这不是我们想要的
  • 二分查找算法,显然是用来查找的算法,我们的目的也算是查找。如果你看过我的上一篇二分查找的文章,里边有说到什么情况下会想到用二分查找,比如我们要查找的一系列数是有序的等,我们要求x的平方根,那肯定在[1, x]这个区间找(x>1),它显然是有序的。这自然 会想到用二分来查找
  • 使用二分查找算法,需要两个游标low和high。需要考虑他们的初始值是什么?以及当mid不满足时,low和hight如何变化?
  • 既然是求x的平方根,x的值有两种情况。第一种是x<1,这种情况,我们要求的结果肯定在[0, 1]这区间内,所以就可以初始化low = 0,hight=1,那mid就为(low+hight)/2
  • x的第二种情况就很简单了,当x>1时,它的平方根的值肯定在[1, n]区间内,所以low = 1, high=x,mid = (low+hight)/2
  • 不难想到,当x-mid*mid < 0时,说明mid太大,那此时我们就应该在[1, mid]之间找,即,此时让hight=mid-1
  • 如果x-midmid > 0,这时要考虑x-midmid是否大于我们要求的精度,如果大于这个精度,那此时low = mid+1
  • 有了以上这些条件,基本上这道题就出来了。如果你按照上边的思路把代码写出来之后会发现是有问题的,当x<1的时候程序就不能正常运行了。原因是low和high变化的时候,如果x<1的时候,结果肯定是小于1的,如果直接让high或low为mid加1或减1肯定就不对了
  • 因此,当x-mid*mid < 0时,应该让high=(mid+high)/2

代码实现


func SolutionSqrt(num float64, precision float64) float64 {
  if num < 0 {
    fmt.Println("参数不合法")
    return -1.000
  }

  var low,high float64
  if num > 1 {
    low = 1
    high = num
  } else {
    low = num
    high = 1
  }

  return Sqrt(num, low, high, precision)
}

func Sqrt(num float64, low float64, high float64, precision float64) float64 {
  mid := (low+high) / 2

  if num - (mid * mid) < 0 {
    return Sqrt(num, low, (mid+high)/2, precision)
  } else {
    if num - (mid * mid) > precision {
      return Sqrt(num, (low + mid)/2, high, precision)
    }

    return mid
  }
}

有疑问加站长微信联系(非本文作者)

本文来自:Segmentfault

感谢作者:书旅

查看原文:LeetCode069-x的平方根-easy

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:701969077

132 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传